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

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;
}
0

Podaj najpierw Twój kod.

0
serek napisał(a):

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

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;
}
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;
}
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

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

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