lite av tanken av sidor liknade project euler är väl att man ska klura på problemen själv men men...
du har krånglat till det och därför har det smygit in sig massa onödiga lösningar och lyckats försumma styrkan i algoritmen...
för det första vet vi att 0 och 1 inte är primtal, likväl som att 2 är det... eftersom första rundan (då man kontrollerar 2) är den mest krävande kan man inkludera den i loopen som förbereder arrayn. Så istället för:
for(int i=0; i<1000000; i++)
tal[i]=true;
som sätter alla värden i arrayen till true så är
for(int i = 3; i < 1000000; i++){
tal[i] = i%2==1;
}
bättre då man som sagt inkluderar första körningen i förberedelserna... kom ihåg att summa-variabeln ska inledas på 2 istället för 0 om man kör med denna metod...
vidare så är själva körningen väldigt konstig och som sagt så utnyttjar den inte styrkan i algoritmen... när du hittar ett primtal så vet du att alla tal som har det talet som primtalsfaktor inte är ett primtal, därmed är if((k%temp==0&&k!=temp)||(k==1)) onödigt då den testar något som du redan vet...
Det du ska göra är att gå igenom hela arrayn, om du finner ett primtal vet du att alla efterföljande tal som är i det talets "gångertabell" inte är primtal... så om du hittar 5 som primtal vet du att 10, 15, 20, 25, 30 osv inte är det, det faktumet utnyttjar du inte...
hur man vet att ett tal är ett primtal är genom att stega genom de tidigare talen i arrayn och om inget tidigare har "eliminerat" talet så är det ett primtal, det är ganska enkelt att förstå varför... Om man gått igenom alla mindre primtal och dessa inte utgör en primtalsfaktor i talet så betyder det att det måste finnas två eller fler större primtal som multiplicerat med varandra blir talet (alltså x*y=z när z<y<x ), men detta är ju självklart omöjligt... alltså kan inte talet ha några primtalsfaktorer (annat än sig själv)...
Vi börjar därför på minsta okontrollerade talet, alltså 3 eftersom vi avklarade 2 i förberedelserna... vi ser att 3 är "oeliminerat" alltså ett primtal... Vi börjar stega och eliminierar alla 3*n upp till 1000000, går till nästa okontrollerade talet, alltså 4. vi ser att det är eliminerat, alltså inte ett primtal och går vidare...
(man kan förkorta det ytterligare lite då man kan börja elimineringsstegningen först vid kvadraten av primtalet eftersom alla tidigare garanterat har blivit eliminerade av tidigare primtal, t.ex. vid 5 kan man börja på 25 eftersom 10 blivit eliminerat av 2*5 (när man hittade primtalet 2), 15 av 3*5 och 20 av 2*10. av samma anledning behöver man bara köra till roten av 1000000 för att garanterat ha eliminerat alla komposittal...)
till sist har vi din summering som är lite överföldig, varför inte summera allt eftersom du hittar primtalen...
om vi sätter det i kod blir det nått så här:
ulong summa = 2;
bool tal[1000000];
for(int n = 3; n < 1000000; n++){
tal[n] = n%2==1;
}
for(int n = 3; n < 1000000; n++){
if(tal[n]){ //n är ett primtal
summa += n;
for(int m = n*n; m < 1000000; m+=n){ //stegar igenom alla tal som har n som primtalsfaktor
tal[m] = false;
}
}
}
cout<<"summan är: "<<summa<<endl;
system("PAUSE");
return EXIT_SUCCESS;
edit: kom på att det antagligen blir overload på int m = n*n när n börjar närma sig miljonen så borde byta ut den forloopen med:
if(n < 1000){ //kontrollerar om "elimination" är nödvändigt
for(int m = n*n; m < 1000000; m+=n){ //stegar igenom alla tal som har n som primtalsfaktor
tal[m] = false;
}
}
