kako definirtati prastevilo

Zanima me, ce obstaja kaksna funkcija za izracun prastevila. Vhod je med stevilom 5 in 15.Ponajdi prastevila po vrstnem redu po velikosti.


Hvala

Kako programsko (v c++)ugotovimo, da je neko število praštevilo?
primer: vnesemo prvo število 1 ,
drugo vnešeno stevilo je 30. Izpiši vsa praštevila med 1 in 30 !

recimo

yahoo power

Takole naredi.

1) Zapiši število 2 v memory.
1) Začni pri številu 3.
2) Preveri če je praštevilo.
3) Če je, zapiši v memory.
4) Povečaj število za 2.

Kako preveriš, če je praštevilo.
1) Deliš željeno število z vsemi števili, ki so v memoryju, do vključno s korenom danega števila. Če nikjer ne dobiš celoštevilčne rešitve, je število praštevilo.

To bi moralo zadostovati za majhna števila (do nekje 16 milijonov ;-))

Moja rešitev je tukaj malo boljša, ker gre po principu rešeta ...

two=2; 
 index=0; 
 sieve[index]=two; 
 index=1; 
 sieve[index]=two; 
 primecandidate=two<<index; 
 while (primecandidate<=upto) { 
 sieve[primecandidate]=index; 
 primecandidate=primecandidate+two; 
 } 
 two^=1; 
 while (two<upto) { 
 primecandidate=two*two; 
 if (primecandidate>upto) { 
 break; 
 } 
 critticall1=two<<index; 
 sieve[primecandidate]=index; 
 primecandidate=primecandidate+critticall1; 
 two+=4; 
 while (primecandidate<=upto) { 
 sieve[primecandidate]=index; 
 primecandidate=primecandidate+critticall1; 
 } 
 primecandidate=two*two; 
 critticall1=sieve[two]; 
 if (critticall1<index) { 
 critticall1=two<<index; 
 while (primecandidate<=upto) { 
 sieve[primecandidate]=index; 
 primecandidate=primecandidate+critticall1;
 } 
 } 
 two^=2; 
 }

// reseto optimizirano

Ne zato. Pač pa ker je vsaj en deljitelj <= korenu, če deljitelj je.

V C++ sem nasel zelo elegantni algoritem za izracun prestevila. Namesto staticne array uporavlja vektor iz STL ali MFC tako, da omogoca generirati poljudno veliko prastevil. (omejitev je velikost vasega int.

Ce nimate STL-a ali MFC-ja naredite staticni array namesto
      vector <boo> S(N, true);

1 #include <iostream>
2 #include <vector>
3 #include <math.h>
4
5 using namespace std;
6
7 int main() {
8 cout << "To enter all prime numbers < N, enter N: ";
9 long N, i, sqrtN, count = 0, j;
10 cin >> N;
11 sqrtN = int(sqrt(N)) + 1;
12 vector<bool> S(N, true);
13
14 // Initially, all S[i] are true.
15 // S[i] = false if and when we find i is not a prime number.
16
17 for (i=2; i < sqrtN; i++)
18 if (S[i]) for (int j=i*i; j<N; j+=i) S[j] = false;
19
20 for (i=2; i<N; i++) if (S[i]) { j = i; count++; }
21
22 cout << "There are " << count
23 << " prime numbers less than " << N << ".\n";
24 cout << "Largest prime number is " << j << "." << endl;
25 return 0;
26 }

/////// INPUT-OUTPUT //////////////////////////////////
///////////////////////////////////////////////////////
// To enter all prime numbers < N, enter N: 1000000
// There are 78498 prime numbers less than 1000000.
// Largest prime number is 999983.

Good luck,