Programozás

[Csokibácsi]

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