Forum » Programiranje » kako definirtati prastevilo
kako definirtati prastevilo
![](https://static.slo-tech.com/stili/avatar_gray.gif)
bombacina ::
Zanima me, ce obstaja kaksna funkcija za izracun prastevila. Vhod je med stevilom 5 in 15.Ponajdi prastevila po vrstnem redu po velikosti.
Hvala
Hvala
![](https://static.slo-tech.com/stili/avatar_gray.gif)
Thomas ::
A bi bil lahko tako dober, pa reformuliral svoje vprašanje, ker ga ne zastopim dobro.
Man muss immer generalisieren - Carl Jacobi
![](https://static.slo-tech.com/stili/avatar_gray.gif)
bombacina ::
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 !
primer: vnesemo prvo število 1 ,
drugo vnešeno stevilo je 30. Izpiši vsa praštevila med 1 in 30 !
![](https://static.slo-tech.com/stili/avatar.gif)
Ziga Dolhar ::
Algoritem za preverjanje "praštevilskosti" je enkrat v forumu že napisal Thomas. Prebrskaj malo po njegovih temah :).
https://dolhar.si/
![](https://static.slo-tech.com/stili/avatar.gif)
snow ::
Obstajajo algoritmi za preverjanje če je število praštevilo. Link.
Izračun praštevila... pa ne pomeni po moje nič.
Podobno kot je včeraj en na radiu spraševal kaj je to pi.
Ena ni vedela, druga je rekla da je to nekaj pri krogu, tretja pa reče: "Pi je ploščina kroga".
Izračun praštevila... pa ne pomeni po moje nič.
Podobno kot je včeraj en na radiu spraševal kaj je to pi.
Ena ni vedela, druga je rekla da je to nekaj pri krogu, tretja pa reče: "Pi je ploščina kroga".
![:D](https://static.slo-tech.com/smeski/icon_biggrin.gif)
Random mutation plus nonrandom cumulative natural selection - Richard Dawkins
![](https://static.slo-tech.com/stili/avatar_gray.gif)
Sergio ::
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 ;-))
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 ;-))
Tako grem jaz, tako gre vsak, kdor čuti cilj v daljavi:
če usoda ustavi mu korak,
on se ji zoperstavi.
če usoda ustavi mu korak,
on se ji zoperstavi.
![](https://static.slo-tech.com/stili/avatar_gray.gif)
frenk ::
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.
a ne do polovice števila in ne do korena števila
![:\](https://static.slo-tech.com/smeski/icon_rolleyes.gif)
![](https://static.slo-tech.com/stili/avatar_gray.gif)
Sergio ::
Moja rešitev je tukaj malo boljša, ker gre po principu rešeta ...
Tako grem jaz, tako gre vsak, kdor čuti cilj v daljavi:
če usoda ustavi mu korak,
on se ji zoperstavi.
če usoda ustavi mu korak,
on se ji zoperstavi.
![](https://static.slo-tech.com/stili/avatar_gray.gif)
Thomas ::
two=2;// reseto optimizirano
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;
}
Man muss immer generalisieren - Carl Jacobi
![](https://static.slo-tech.com/stili/avatar_gray.gif)
Thomas ::
Ne zato. Pač pa ker je vsaj en deljitelj <= korenu, če deljitelj je.
Man muss immer generalisieren - Carl Jacobi
![](https://static.slo-tech.com/stili/avatar_gray.gif)
Thomas ::
primecandidate=2; //the first or seed prime
one=1; //one (1)
while (primecandidate<upto) {
nonprime=primecandidate+primecandidate;
while (nonprime<=upto) {
sieve[nonprime]=one;
nonprime=nonprime+primecandidate;
}
primecandidate++;
} // to je pa original, neoptimizirana koda.
Man muss immer generalisieren - Carl Jacobi
Zgodovina sprememb…
- spremenil: Thomas ()
![](https://static.slo-tech.com/stili/avatar_gray.gif)
ooux ::
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);
Good luck,
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,
![:)](https://static.slo-tech.com/smeski/icon_smile.gif)
Vredno ogleda ...
Tema | Ogledi | Zadnje sporočilo | |
---|---|---|---|
Tema | Ogledi | Zadnje sporočilo | |
» | pra števila.. (strani: 1 2 )Oddelek: Znanost in tehnologija | 8623 (4962) | Yacked2 |
» | Digitalna evolucija (strani: 1 2 3 4 … 26 27 28 29 )Oddelek: Znanost in tehnologija | 74793 (24962) | pietro |
» | Najhitrejši programski jezik? (strani: 1 2 )Oddelek: Programiranje | 7616 (5436) | Senitel |
» | Generatorji praštevilOddelek: Znanost in tehnologija | 3778 (2682) | Phil |
» | O praštevilih (strani: 1 2 )Oddelek: Novice / Znanost in tehnologija | 6606 (6606) | ovdje kokoš |