Atkin - wo ist der Fehler

[darkeye2]

Hallo, ich hab ein problem, ich brauche sehr viele primzahlen, hab den aktin implimentiert und die klasse smallboolean geschreiben, da ich sonst speicherprobleme hatte ... nun geht alles gut, bis ich ne gewisse anzahl hab, dann kommen fehler rein (zahlen, die keine primzahlen sind).

Atkin:

import java.text.SimpleDateFormat;
import java.util.ArrayList;
import java.util.Date;


public class Atkin
{
    private  ArrayList<Long> primes;
    private long limit;
    SimpleDateFormat sdf = new SimpleDateFormat("dd.MM.yyyy HH:mm:ss");
    protected boolean tmp;

    public Atkin(long limit)
    {
        this.limit = limit;
        primes = new ArrayList<Long>();
        System.out.println("Startzeit: " + sdf.format(new Date()));
        FindPrimes();
    }

    public ArrayList<Long> getPrimes(){
    	return primes;
    }

    private void FindPrimes()
    {
        SmallBoolean isPrime = new SmallBoolean((limit +1));
        double sqrt = Math.sqrt(limit);

        for (long x = 1; x <= sqrt; x++){
            for (long y = 1; y <= sqrt; y++)
            {
                int n = (int) (4 * x * x + y * y);
                if (n <= limit && (n % 12 == 1 || n % 12 == 5)){
                	tmp = isPrime.get(n)^true;
                	isPrime.set(n, tmp);
                }

                n = (int) (3 * x * x + y * y);
                if (n <= limit && n % 12 == 7){
                	tmp = isPrime.get(n)^true;
            		isPrime.set(n, tmp);
                }

                n = (int) (3 * x * x - y * y);
                if (x > y && n <= limit && n % 12 == 11){
                	tmp = isPrime.get(n)^true;
            		isPrime.set(n, tmp);
                }
            }
        }

        for (long n = 5; n <= sqrt; n++)
            if (isPrime.get(n))
            {
                int s = (int) (n * n);
                for (long k = s; k <= limit; k += s)
                	isPrime.set(k, false);
            }
                
        primes.add((long)2);
        primes.add((long)3);
        for (long n = 5; n <= limit; n++)
            if (isPrime.get(n)){
                primes.add(n);
            }
    }
    
	public static void main(String[] args) {
		new Atkin(10000000);
		
	}
    
}

SmallBoolean:

public class SmallBoolean {
	int[] puffer;
	
	SmallBoolean(long limit){
		int kit=0;
		if(limit <32){
			kit = 1;
		}else if((limit%32) == 0){
			kit = (int)limit/32;
		}else if((limit%32)>0){
			kit = (int) (limit/32)+1;
		}else{
			System.out.println("Inizialisierung fehlgeschlagen: "+limit+" => "+(limit%32));
		}
		
		puffer = new int[kit];
	}
	
	public boolean get(long pos){
		int kit=0;
		if(pos <32){
			kit = 0;
		}else if((pos%32) == 0){
			kit = (int)pos/32;
			kit--;
		}else if((pos%32)>0){
			kit = (int) (pos/32)+1;
			kit--;
		}else{
			System.out.println("Ungültige get-Position: "+pos+" => "+(pos%32));
		}
		
		int  getter = (puffer[kit] >> (pos % 32))&1;
		//System.out.println(getter+" gefragete Possition: "+pos%32+" Wert: "+puffer[kit]);
		if( getter == 1){
			return true;
		}else{
			return false;
		}
	}
	
	public void set(long pos, boolean status){
		int kit=0;
		if(pos <32){
			kit = 0;
		}else if((pos%32) == 0){
			kit = (int)pos/32;
			kit--;
		}else if((pos%32)>0){
			kit = (int) (pos/32)+1;
			kit--;
		}else{
			System.out.println("Ungültige set-Position: "+pos+" => "+(pos%32));
		}
		//System.out.println(puffer[kit]);
		int setter = (puffer[kit] >> (pos % 32))&1;
		//System.out.println(setter+" "+status+" gefragete Possition: "+pos%32+" Wert: "+puffer[kit]);
		  if(!status && setter ==1) {
			    // 0
			    puffer[kit] = puffer[kit] & ~(1 << (pos % 32));
		  } else if(status) {
			    // 1
			    puffer[kit] = puffer[kit] | (1 << (pos % 32));
		  }
		  //System.out.println(puffer[kit] & (1 << (pos % 32)));
	}

}

Hoffe jemand findet den fehler

 

[Marco13]

Kann vielleicht später nochmal schauen (obwohl sich auf alles was mit Primzahlen zu tun hat noch andere stürzen werden ), aber nur nebenbei: SmallBoolean ist ein abgespecktes BitSet (Java Platform SE 6) ?!

 

[XHelp]

Wie könnte man denn den Fehler nachstellen? Bzw was heißt denn "gewisse Anzahl"?
Wenn man es bis 10000000 aussiebt, dann ist die 664579te Primzahl: 9999991 und das stimmt auch.
Diese Tatsache ist überhaupt nicht aussagekräftig, aber wenn er andere Zahlen reingenommen hätte, dann hätte ich erwartet, dass sich der Index verschiebt.

P.S. die 26milionste Primzahl stimmt auch.
Wie entscheidest du, dass die Zahlen, die drin sind, keine Primzahlen sind?

 

[darkeye2]

wenn ich das ganze mit 80000000 durchlaufen lasse ist unter den ersten 100 primzahlen kein fehler (habs durchprobiert) doch wenn ich dann 1 000 000 000 primzahlen generieren lasse, sind bereits unter den ersten 100 mehrere zahlen dabei, die keine primzahlen sind (weil die sich definitief durch zahlen teilen lassen) und bei einem durchlauf bis 900 000 000 sind auch bereits unter den ersten 100 einige fehler, aber weniger als bei einer milliard, wenn ich mich recht errinere rutscht da z.b. die 481 rein, obwohl es keine primzahl ist (da 481/13 = 37) von daher bin ich mir zimlich sicher, dass da was net stimmt, aber ich komme einfach nicht dahinter, woran das liegt (laut irgend einer seite, die ich net mehr finde haben die dort den sieb des atkin bis 1 000 000 000 000 durchlaufen lassen und haben keine fehler drin gehabt, ich will es ja nur bis zu ner milliard haben und kriege bereits vorher schon fehler rein...)

 

[Marco13]

Schau dir das mit dem SmallBoolean nochmal an. Ich habe es nicht im Detail nachvollzogen, aber schon ein ">>" sieht verdächtig aus...

 

[Marco13]

Nee. Kommando zurück:

for (long x = 1; x <= sqrt; x++){
            for (long y = 1; y <= sqrt; y++)
            {
                int n = (int) (4 * x * x + y * y);

Für einen int wird das n da IMHO zu groß...?!

 

[darkeye2]

hmm, ich glaub du hast recht, hab mal durch long ersetzt, sollte jetzt klappen, wenn es daran gelegen hat, werde es mal ausprobieren.

Schonmal danke für die idee

 

[Marco13]

Ganz nebenbei, und da du das offenbar nicht als Hausaufgabe implementierst: Solche Sachen wie BigInteger (Java Platform SE 6) kennst du?

 

[darkeye2]

hast recht, ist keine hausaufgabe, aber ich brauche die primazahlen in der richtigen reihenfolge, und aufeinanderfolgend, um etwas anderes aus zu probieren, falls du das kennst:
es geht um die annäherung an pi durch verwendung von primzahln, deswegen brauch ich auch so viele