Program, który dla liczby parzystej przedstawia wszystkie możliwe jej rozkłady na sumę dwóch liczb pierwszych. C++.

Odpowiedz Nowy wątek
2019-10-16 18:21
0

Problem jest podany najogólniej w temacie - mam napisać program w C++, który dla dowolnej (podanej przez użytkownika) liczby parzystej przedstawia wszystkie możliwe jej rozkłady sumę dwóch liczb pierwszych. Zadanie w swoim zamyśle nie powinno być trudne - obejmować ma podstawy programowania. Może ktoś pomoże, podda pomysł? Mój dotychczasowy kod jest poniżej. Pomyślałem, żeby dla podanej przez użytkownika liczby podać wszystkie liczby pierwsze mniejsze lub równe jej - to napisałem. Co dalej?
Pozdrawiam.

#include <iostream>
using namespace std;
int main()
{
    int n;
    int k=1;
    bool p;

    cin>>n;
    int tab[n];

    for(int i = 1; i <= n; i++)
    {
        p = true;

        for(int j = 2 ; j < i; j++){
            if( i % j == 0){
                p = false;
            }
        }

        if(p == true){
            cout<<i<<" ";
            tab[k]=i;
            k++;
        }
    }
    cout<<endl;

    return 0;
}
edytowany 2x, ostatnio: cerrato, 2019-10-16 19:40

Pozostało 580 znaków

2019-10-16 18:30
0

Podaj najpierw Twój kod.

Pozostało 580 znaków

2019-10-16 18:40
0
serek napisał(a):

Podaj najpierw Twój kod.
Ok, podałem swój początek.

Pozostało 580 znaków

2019-10-16 20:01
0

@tagtak: "Pomyślałem, żeby dla podanej przez użytkownika liczby podać wszystkie liczby pierwsze mniejsze lub równe jej - to napisałem" - 1 to nie liczba pierwsza. Najlepiej Wyłap te liczby do jakiejś struktury (chociażby tablicy), a potem już łatwo sprawdzić wszystkie sumy. To jest naiwne rozwiązanie, szybciej byłoby uzyć Sita Erastotenesa do znalezienia liczb pierwszych i potem szukać sum.

#include<iostream>
using namespace std;

int main(int argc, char **argv){
    int number = 10;
    int primes [] = {2, 3, 5, 7};
    int length = 4;
    for (int i = 0; i < length; ++i) {
        for (int j = i; j < length; ++j){
            if (primes[i] + primes[j] == number)
                cout << primes[i] <<" "<<primes[j];
        }
        cout <<"\n";
    }
    cout << "\n";
    return 0;
}

O rzesz! Kwadratowy koszt wymodziłeś! Znowu najpierw kodzimy później się pomyśli ;P - _13th_Dragon 2019-10-16 20:56
Ano kwadratowy, napisałem, że to rozwiązanie naiwne. - lion137 2019-10-16 21:01
Przynajmniej leć z dwóch stron, jak za duże to z prawej, jak za mało to z lewej i już masz liniowy. - _13th_Dragon 2019-10-16 21:03
Będzie szybciej,ale czy liniowy? - lion137 2019-10-16 21:05
Owszem bo koniec kiedy zejdą się razem, czyli w sumie pętla zrobi N kroków, a że kroki raz z lewej raz z prawej to nie ma znaczenia. - _13th_Dragon 2019-10-16 21:07

Pozostało 580 znaków

2019-10-16 21:35
0

Czyli miej więcej tak, wygląda, że, rzeczywiście, złożoność jest liniowa (nie licząc isPrime), z tym: "Goldbach conjecture prooved" to żart - zakładamy, że liczba będzie parzysta:

#include <iostream>
using namespace std;

int isPrime(int n) {
    if (n <= 3) return n > 1;
    else if (n % 2 == 0 || n % 3 == 0) return 0;
    int i = 5;
    while (i * i <= n) {
        if (n % i == 0 || n % i + 2 == 0)
            return 0;
        i += 6;
    }
    return 1;
}
void testIntegerAsSumOfTwoPrimes(int n) {
    int i;
    int c = 0;
    for (i = 2; i <= n / 2; ++i) {
        if (isPrime(i)) {
            if (isPrime(n - i)) {
                cout << n << " = " << i << " + " << n - i <<"\n";
                c = 1;
            }
        }
    }
    if (c == 0) {
        cout << "Goldbach conjecture prooved:)\n";
    }
}

int main(int argc, char **argv){
    int number;
    cin >> number;
    cout << "\n";
    testIntegerAsSumOfTwoPrimes(number);
    return 0;
}

Nie! teraz znowu zrobiłeś koszt O(n^2) !! - _13th_Dragon 2019-10-17 00:00
Co ty, na fazie Jesteś? isPrime ma sqrt(n), w pętli jest liczone dwa razy, co daje, max, sqrt(n) * sqrt(n) * n / 2! - lion137 2019-10-17 00:09
sqrt(n) * sqrt(n) = n zaś n*n = n^2 stałe się nie liczą - _13th_Dragon 2019-10-17 00:10
Ok, nie piszę tu pracy naukowej z tabelkami, i tak dalej, ale ralnie O(n^3) to będzie pesymistycznie; zresztą dać tu isPrime = Miller Rabin, czyli, dla longów czs stały, to mamy algorytm O(n/2). - lion137 2019-10-17 00:30
Nie ma czegoś takiego jak O(n/2) stałe się nie liczą. - _13th_Dragon 2019-10-17 01:12

Pozostało 580 znaków

2019-10-17 11:26
1

Sito z pomocą constexpr (więc limit do 2900 :()
pozwala na złożoność (zakładając stały czas dla EratostenesSive::next): O(\frac{n}{log n})

Jeśli dobrze liczę, to EratostenesSive::next ma złożoność O(log n), więc całkowicie wychodzi: O(n).

/* constexpr Eratostenes sive */
/* and count how many times X can be decomposed to sum of two primes */
#include <iostream>
#include <array>
#include <exception>
#include <algorithm>
#include <optional>

template<size_t N>
class EratostenesSive
{
public:
    constexpr EratostenesSive()
        : oddPrimes{}
    {
        std::fill(oddPrimes.begin(), oddPrimes.end(), true);
        oddPrimes[0] = false;

        for (size_t p = 3; p * p <= N; p += 2) {
            if (oddPrimes[p/2]) {
                for (size_t i = p * p; i <= N; i += 2 * p) {
                    oddPrimes[i/2] = false;
                }
            }
        }
    }

    bool isPrime(size_t x) const
    {
        if (x < 2) return false;
        if (x == 2) return true;
        if (x > max()) throw std::invalid_argument("Sive limit reached");
        return x%2 != 0 && oddPrimes[x/2];
    }

    bool isPrimeInRange(size_t x) const
    {
        return x <= max() && isPrime(x);
    }

    std::optional<size_t> next(size_t x) const
    {
        auto index = (x + 1) / 2;
        while (index < oddPrimes.size() && !oddPrimes[index]) ++index;
        if (index < oddPrimes.size()) return index * 2 + 1;
        return {};
    }

    constexpr size_t max() const {
        return N | 1;
    }

private:
    std::array<bool, (N + 1) / 2> oddPrimes;
};

constexpr auto primes = EratostenesSive<2900>{};

class CountIsSumOfTwoPrimes
{
public:
    CountIsSumOfTwoPrimes(size_t x) : x(x)
    {
    }

    size_t count() const {
        if (x % 2 == 1) return primes.isPrime(x - 2);

        size_t result = 0;
        size_t p = 3;

        while (p * 2 <= x) {
            result += primes.isPrime(x - p);
            p = primes.next(p).value();
        }

        return result;
    }

private:
    size_t x;
};

int main()
{
    size_t x;

    while (std::cin >> x) {
        std::cout << x << " :";
        CountIsSumOfTwoPrimes twoPrimessums{ x };

        std::cout << twoPrimessums.count() << '\n';
    }
    return 0;
}

https://wandbox.org/permlink/gNB9QLUybY8V8Lvd


Jeśli chcesz pomocy, NIE pisz na priva, ale zadaj dobre pytanie na forum.
edytowany 4x, ostatnio: MarekR22, 2019-10-17 11:48

Pozostało 580 znaków

2019-10-17 12:07
1

Ja widzę to jakoś tak:

#include <iostream>
#include <vector>
using namespace std;

class SumTwoPrimes
{
    private:
    size_t n;
    vector<size_t> primes,lows;
    public:
    SumTwoPrimes(size_t n):n(n) 
    {
        PrimesOver2();
        SumPrimes();
        primes.resize(0);
    }
    size_t oposite(size_t p)const { return n-p; }
    const vector<size_t> &list()const { return lows; }
    protected:
    void PrimesOver2()
    {
        vector<bool> bin(n+1);
        for(size_t i=3;i<=n;i+=2)
        {
            if(!bin[i])
            {
                primes.push_back(i);
                for(size_t k=i<<1;k<=n;k+=i) bin[k]=true;
            }
        }
    }
    void SumPrimes()
    {
        for(int fr=0,bk=primes.size()-1;fr<=bk;)
        {
            size_t pfr=primes[fr],sum=pfr+primes[bk];
            if(sum>n) --bk;
            else if(sum<n) ++fr;
            else
            {
                lows.push_back(pfr);
                ++fr;
                --bk;
            }
        }
    }
};

int main() 
{
    SumTwoPrimes stp(1000);
    for(auto p:stp.list()) cout<<p<<" + "<<stp.oposite(p)<<endl;
    return 0;
}

https://ideone.com/ly8V7z


Wykonuję programy na zamówienie, pisać na Priv.
Asm/C/C++/Pascal/Delphi/Java/C#/PHP/JS oraz inne języki.

Pozostało 580 znaków

Odpowiedz
Liczba odpowiedzi na stronę

1 użytkowników online, w tym zalogowanych: 0, gości: 1, botów: 0