Omówienie zadania “A. Noldbach problem”

Omówienie zadania “A. Noldbach problem”

Szczegółowe omówienie zadania A. Noldbach problem.
Zadanie ćwiczy zrozumienie Sita Eratostenesa.
Szczegółowe omówienie rozwiązania zdania oraz Sita Eratostenesa:
https://youtu.be/tuXRPTYIS8E?t=1644
Poniżej kod wzorcowy do zadania użyty w powyższym omówieniu:
#include <bits/stdc++.h>
using namespace std;

const int MAX_PRIME = 1e3 + 7; // 1000 + 7 = 1007
int sito [MAX_PRIME]; //na poczatku wszystkie wartosci sa wyzerowane na przyklad: sito[3] = 0, sito[6] = 0

void Sito() {
 int i,j, max_analizy;
 
 max_analizy = sqrt(MAX_PRIME) + 1;
 sito[0] = 1;
 sito[1] = 1;
 for (i=2; i<max_analizy; ++i) {
 	if (sito[i] == 1) {
 	   continue;	
 	}
 	for (j=i*i; j<MAX_PRIME; j=j+i) {
 	   sito[j] = 1;	
 	}
 }
 
}

int main () {
 ios_base::sync_with_stdio(0);
 cin.tie(0);
 cout.tie(0);
 
 int max_zakres;
 int k, wynik;
 int suma_3_liczb;
 int poprzednia_pierwsza, i;
 
 Sito();	
 
 cin >> max_zakres;
 cin >> k;
 
 wynik = 0;
 poprzednia_pierwsza = 2;
 for (i=3; i<=max_zakres; ++i) {
    if ( sito[i] == 1 )	{
       continue;	
    }
    suma_3_liczb = poprzednia_pierwsza + i + 1;
    if ( sito[suma_3_liczb] == 1 ) {
    	poprzednia_pierwsza = i;
    	continue;
    }
    if ( suma_3_liczb > max_zakres) {
        break;	
    }
    ++wynik;
    poprzednia_pierwsza = i;
 }
 
 if (wynik >= k) {
 	cout << "YES\n";
 } else {
 	cout << "NO\n";
 }
 
 return 0;
}

Nie dodano jeszcze komentarza, rozpocznij dyskusję pierwszy.

Dodaj komentarz