Nekromanti [C++]Vektorer och gojs

[Fienden]

Åh herre gud att jag missade det. Det ska ju vara *=. Suck. Tack så mycket, Tony.

 

[Troberg]

Jag har ingen lösning på ditt aktuella problem, men jag tycker din algoritm är lite ineffektiv.

Jag skulle utnyttjat följande:

Ett tal är ett primtal om det inte är jämnt delbart med något primtal <=roten ur talet.

Så, ta, i tur och ordning alla udda tal (varför testa jämna, när vi vet att det inte finns jämna primtal (undantaget 2)), och testa om de är jämnt delbara med alla primtal vi hittat tidigare som är <= roten ur talet vi testar. Så fort något är jämnt delbar slutar vi testa på det talet, då är det inte primtal. Hittar vi ett primtal så lagrar vi undan det i en vektor så att vi kan testa mot det sedan.

Borde vara betydligt snabbare, speciellt när man kommer upp i stora tal. Dessutom, du behöver inte lagra talen som inte är primtal.

 

[anth]

Så, ta, i tur och ordning alla udda tal (varför testa jämna, när vi vet att det inte finns jämna primtal (undantaget 2))

Går att snabba upp ytterligare med lite mer kod.
Strunta i att testa tal delbara med 2 och 3.
Testa 2 och 3 separat.
Börja med 5 och iterera sedan omväxlande med +2, resp +4.
5
+2
7
+4
11
+2
13
+4
17
+2
19
+4
23
o.s.v.

 

[Fienden]

Inte för att jag har något emot att ni föreslår bättre algoritmer, men vi ombads faktiskt använda just den metoden (Eratosthenes såll heter den ju?) som jag utnyttjar i koden! Tack i alla fall.

 

[Spider Jerusalem_UBBT]

Inte för att jag har något emot att ni föreslår bättre algoritmer, men vi ombads faktiskt använda just den metoden (Eratosthenes såll heter den ju?) som jag utnyttjar i koden! Tack i alla fall.

<div class="ubbcode-block"><div class="ubbcode-header">Code:</div><div class="ubbcode-body ubbcode-pre" ><pre>#include<iostream>
#include<cstdlib>
using namespace std;

int main(){
int num, numprimes = 1;
int *primes,*temp;
bool prime;

primes = (int*)malloc(1*sizeof(int));
primes[0] = 2;

cout << "Please enter a positive integer" << endl;
cin >> num;

for(int i = 3; i <= num; i++){
prime = true;
for(int n = 0; n < numprimes; n++){
if(i % primes[n] == 0){
prime = false;
break;
}
}
if(prime){
cout << i << " is prime" << endl;
temp = (int*)realloc(primes,(++numprimes)*sizeof(int));
if(temp != primes) free(primes);
primes = temp;
primes[numprimes-1] = i;
}
}

return 0;
}</pre></div></div>

Det här är ett snabbt sätt att kolla om det är prim tal, vad koden gör är att du petar in ett possitivt tal och så spottar den ur sig alla primtal.