Quote:
Originally Posted by BimmBimm
Az általam ismert legjobb módszer, ha csak a szám gyökéig keresed az osztóit.
PHP Code:
int isprime(unsigned int n)
{
unsigned int i;
unsigned int maxi=sqrt(n);
for (i=2;i<=maxi;i++)
{
if (n%i==0) return 0;
}
return 1;
}
(ez c kód)
|
Ez a sima osztogatós módszerhez képest majdnem ~250x-es gyorsulás (900000-ig kerestem a legnagyobb prímszámot).
Ennél még gyorsabb Eratosztenész szitálós módszere, 10 millás plafonnal ~30-35x gyorsabb mint a gyökös-osztós.
Igaz, durván zabálja a memóriát ha nagy számot keresünk, de ezzel akár lehet trükközni is
1 milliárdos limitnél 980MB RAM ugrik át foglaltba, viszont gyorsan megvan az eredmény, míg a gyökösnél a 100 millához 5 perc után már nem volt türelmem.
PHP Code:
int big_prime(int n)
{
int i, j, bigpr;
char tomb[n];
for (i = 0; i < n; i++) tomb[i] = 1;
for(i = 2; i < n; i++) {
if (tomb[i] == 1) {
for(j = i * 2; j < n; j += i) tomb[j] = 0;
}
}
for(i = 1; i < n; i++)
if(tomb[i] == 1) bigpr = i;
return bigpr;
//tomb tartalmazza az osszes n-nel kisebb primet, nekem csak a legnagyobb kellett
//lehet jatszani unsigned long long valtozokkal is ...
}
(eziscébenvan)
A legjobb az AKS algoritmus, de azt próbálja ki más
A legnagyobb ismert prím pedig a 2^43112609 − 1
