Finde primtal med BigInteger

Jo den hedder modulus.

BigInteger klassen har en mod metode til det samme.

a = b.mod(c);

svarer til

a = b % c;

Altså:

if(no.mod(i).equals(zero))

hvor både no og i er BigInteger og zero er en BigInteger med værdi 0.

1000 tak... Det var 60 lette points til dig :)

if(no.mod(i).equals(BigInteger.ZERO))

jeg så lige at de har lavet en konstant for zero.

Kan du ikke bare kalde:
bi.isProbablePrime(Integer.MAX_VALUE);

Så har du en sandsynlighed på:
1 - 1/2^(2^31-1)  ~ 1

1/2^(2^31-1) er *meget* tæt på 0. Derfor har du en sandsynlighed på næsten 1 for at tallet er et primtal. Jeg tror du skal op i ***meget*** store primtal før den tager fejl.

Jo... Men gad vide hvor stor chancen for at det ikke er et primtal, er i forhold til det største primtal der er fundet indtil videre. Jeg ved ikke hvor stort det største fundne primtal er? er det tæt på eller langt fra ***meget*** :)

Der er brugt mange resourcer på at finde primtal du kan godt regne med at det største
primtal er meget stort.

http://www.cnn.com/2003/TECH/science/12/11/prime.number.ap/

Det pt. største mersenne primtal (2^x - 1) er:
2^20,996,011 - 1

Info:
http://www.mersenne.org/prime.htm

Tallet:
http://mersenne.org/prime6.txt

Hvis du vil finde alle primtal mellem 2 og n kan du gøre følgende (en "si" algoritme - ikke primtal sies væk):

* lav et boolean array af længde n
* markér alle elementer som true (som udgangspunkt er alle tal primtal).
* markér de tal som ikke er primtal med false
  - kør tabellerne fra 2 til kvadratrod n igennem

(der skal tages højde for hvor i tabellen der startes, f.eks. ved 2 tabellen startes ved 4, ved 3 tabellen startes ved 6 osv. - for at undgå at 2 og 3 markeres false.)

Optimeringer:
* når du har kørt 2 tabellen igennem behøver du ikke løbe flere lige tal igennem
* når du har kørt 5 tabellen igennem behøver du ikke løbe flere tal der ender på 5 igennem
* muligvis flere

Arrayet indeholder så alle primtal (de elementer der er true) mellem 2 og n.

Jeg lavede engang følgende lille test:

public class Prime {
    public static void main(String[] args) {
        for(int i = 10; i <= 10000000; i *= 10) {
          prime1(i);
          prime2(i);
        }
    }
    public static void prime1(int n) {
        long t1 = System.currentTimeMillis();
        int count = 0;
        for(int i = 2; i <= n; i++) {
            int maxj = (int) Math.sqrt(i);
            boolean fnd = false;
            for(int j = 2; j <= maxj; j++) {
                if((i % j) == 0) {
                    fnd = true;
                    break;
                }
            }
            if(!fnd) count++;
        }
        long t2 = System.currentTimeMillis();
        System.out.println(count + " of " + n + " by division: " + (t2 - t1));
        return;
    }
    public static void prime2(int n) {
        long t1 = System.currentTimeMillis();
        boolean[] pri = new boolean[n+1];
        for(int j = 0; j <= n; j++) pri[j] = true;
        pri[2] = true;
        for(int i = 2; i <= n; i++) {
            if(pri[i]) {
                for(int j = 2 * i; j <= n; j += i) {
                    pri[j] = false;
                }
            }
        }
        int count = 0;
        for(int j = 2; j <= n; j++) if(pri[j]) count++;
        long t2 = System.currentTimeMillis();
        System.out.println(count + " of " + n + " by flagging: " + (t2 - t1));
        return;
    }
}

resultat idag:

4 of 10 by division: 0
4 of 10 by flagging: 0
25 of 100 by division: 0
25 of 100 by flagging: 0
168 of 1000 by division: 0
168 of 1000 by flagging: 0
1229 of 10000 by division: 16
1229 of 10000 by flagging: 0
9592 of 100000 by division: 94
9592 of 100000 by flagging: 0
78498 of 1000000 by division: 2062
78498 of 1000000 by flagging: 156
664579 of 10000000 by division: 53172
664579 of 10000000 by flagging: 1875

Den er kendt som "The Sieve of Eratosthenes" efter en græsk matematiker
som levede 275-195 BC, så det er absolut ikke en ny opfindelse.

Pænt stort tal...
1000 tak... Det er en fed ide, den med at "si"...

Deraf må man kunne konkludere at flagging udførselsmæssigt er hurtigere.

Men, man skal lige have i baghovedet at der kræves ekstra plads til arrayet.

Si oversættes til sieve på engelsk.

Ja - og man skal hele tiden huske på at fordelen ved sien er når man skal
finde alle primtal op til n.

der findes jo en formel der næsten virker til at beregne primtal... det er vidst noget med at hvis du dividere med 3 og får resten 5 eller 2 så er chancen for primtal stor (= meget sikker) - kan finde ud af den korrekte formel hvis du vil :D

Mon ikke det er en lign. algoritme som findes i BigInteger klassen..