[c++] Ilość liczb pierwszych w przedziale Szybki algorytm...

TU JEST ZAD
Sprowadza sie ono do podania ile liczb pierwszych znajduje sie w przedziale [a, b]. Mój kod na to jest nastepujacy:
#include <iostream> using namespace std; bool tablica[1000001]; main() { int i,j,b,a,k,t; for (i=2; i<=1000001; i++) { if (!tablica[i]) { j = 2*i; while (j<=1000001) { tablica[j] = true; j += i; } } } scanf("%d", &t); while(t--) { k=0; scanf("%d %d", &a, &B); if(a%2 == 0) { if(!tablica[a]) k++; a++; } for (i=a; i<=b; i = i + 2) if (!tablica[i]) k++; printf("%d\n",k); } }

Jednak dla spoja jest on za wolny... :( Jak to przyspieszyc? Przeciez podobno nie ma szybszego algo na l. pierwsze niz sito...

EDIT: Na prośbę pewnej osoby wstawiam rozwiązanie mojego problemu:
#include <iostream> #include <cstdio> using namespace std; bool tablica[1000001]; int ilosc[1000001]; int j, b ,a, k = 0,t, suma; main() { for (int i = 2; i <= 1000001; i++) { if (!tablica[i]) { j = 2*i; while (j <= 1000001) { tablica[j] = true; j += i; } } } for (int i = 2; i <= 1000000; i++) { if(!tablica[i]) k++; ilosc[i] = k; } scanf("%d", &t); while(t--) { scanf("%d %d", &a, &B); if(!tablica[a]) suma = ilosc[b]-ilosc[a]+1; else suma = ilosc[b]-ilosc[a]; printf("%d\n",suma); } system("pause"); }
Użytkownik Kamil Wajda edytował ten post 05 lipiec 2008, 13:45

zanotowane.pl

doc.pisz.pl

pdf.pisz.pl

zsf.htw.pl