velocizzare algoritmo numeri primi

[glukosio]

Ciao a tutti, sto facendo l'esercizio 521 di Project Euler (https://projecteuler.net/problem=521)
In pratica devo sommare i fattori primi più piccoli di tutti i numeri da 2 a 10^12.
Teoricamente è un esercizio banale, praticamente è abbastanza complesso dato che un computer normale ci metterebbe svariate ore se non addirittura giorni per calcolare così tanti numeri!
Il mio codice al momento è questo:

public class e521v2{    public static void main(String[] args){
        int[] primi=new int[9592];
        int y=0;
        long tot=2;
        for(int i=2;i<100000;i++){
boolean flag=true;
            for(int x=2;x<i;x++){
                if(i%x==0){
                    flag=false;
                    break;
                }
            }
            if(flag) primi[y++]=i;
        }

        for(int n=3;n<=Integer.MAX_VALUE-1;n++){
boolean flag=true;
            for(int i=0;i<primi.length;i++){
                if(n%primi[i]==0){
                    flag=false;
                    tot+=primi[i];
                    break;
                }
            }
            if(flag) tot+=smpfint(n);

        }
        for(long n=Integer.MAX_VALUE;n<=1000000000000L;n++){            
boolean flag=true;
            for(int i=0;i<primi.length;i++){
                if(n%primi[i]==0){
                    flag=false;
                    tot+=primi[i];
                    break;
                }
            }
            if(flag) tot+=smpf(n);
        }
        tot=tot%1000000000L;
        System.out.print(tot);

    }

private static int smpfint(int i){
boolean flag=true;
        for(int p=99993;p<Math.sqrt(i)+1;p+=2){

            flag=true;
            for(int x=3;x<Math.sqrt(p);x+=2){
                if(p%x==0){
                    flag=false;
                    break;
                }
            }
            if(flag){
                if(i%p==0){
                    return p;
                }
            }
        }
return i;
    }
private static long smpf(long i){
boolean flag=true;
        for(long p=99993;p<Math.sqrt(i)+1;p+=2){
            flag=true;
            for(long x=3;x<Math.sqrt(p);x+=2){
                if(p%x==0){
                    flag=false;
                    break;
                }
            }
            if(flag){
                if(i%p==0){
                    return p;
                }
            }
        }
return i;
    }
}

e in teoria funziona, solo che non posso aspettare giorni interi per avere una soluzione, e sono sicuro che ci sono altri algoritmi decisamente più veloci!
Al momento ho diviso le funzioni per i valori Int e quelli Long poichè java lavora più lentamente con i Long, risparmiando qualche cosa nelle prime 2^32 iterazioni (non so se ci sono mai arrivato comunque).
Poi ho fatto arrivare i numeri primi alla radice quadrata del numero in questione perchè so che oltre non ce ne sono (spero di non sbagliarmi), ho escluso i numeri pari e sto lavorando per escludere i multipli di 3.
Fatto sta sono sicuro che esiste un algoritmo completamente diverso che calcolerebbe tutto in un istante!

Potrebbe funzionare dargli un array con i primi 1000 numeri primi? così per la maggiorparte si basa sull'array e non sul calcolo?
Qualcuno ha in mente qualcosa che possa aiutarmi a velocizzare il codice? grazie in anticipo!

EDIT:ho fatto un array con i primi 9592 numeri primi (i numeri primi tra 2 e 100.000) e ho reindirizzato il controllo all'array prima di farlo passare alla funzione (modificata anche quella in modo tale da iniziare da 100.000).
ho notato circa il 45% di miglioramento (nei numeri da 0 a 10 milioni), ma non credo che sia abbastanza!
Ho pensato anche di farla multithreading ma non sono ancora molto maneggevole con questo argomento e ho paura di incasinare il tutto non traendo alcun beneficio! Se qualcuno pensa che possa essere una buona idea e può spiegarmi in linea teorica cosa devo fare, mi aiuterebbe assai

[Santino83_02]

dovresti chiedere ad un matematico piu che altro, cmq queste slides sono molto interessanti per il tuo problema: http://www.cli.di.unipi.it/~bodei/CO...etti/primi.pdf

[glukosio]

Grazie mille per la risposta, sì lo so, questo è campo della matematica avanzata, però nei forum di solito c'è tanta di quella gente che sa tutto!!
Comunque nella mia sessione notturna di bazzicamento su google mi sono già imbattuto in quelle slide

[glukosio]

ho modificato un po' il codice velocizzandolo circa di 10 volte! però non è abbastanza: per fare tutto il processo ci metterebbe più di 2 settimane. forse anche 4, non so quanto tanto rallenta aumentando il numero.
Ho provato anche a trascrivere il tutto in C, ma è addirittura più lento di java!

public class e521v2{    
public static void main(String[] args){
        int[] primi=new int[664579];
        primi[0]=2;
        primi[1]=3;
        int y=2;
        long tot=500000000000L;
        for(int i=3;i<10000000;i+=2){
            if(isPrimeint(i)) primi[y++]=i;
        }

        for(int n=3;n<=Integer.MAX_VALUE-1;n+=2){
boolean flag=true;
            if(isPrimeint(n)){
                tot+=n;
continue;
            }
            else{
                for(int i=0;i<primi.length;i++){
                    if(n%primi[i]==0){
                        flag=false;
                        tot+=primi[i];
                        break;
                    }
                }
                if(flag) tot+=smpfint(n);
            }

        }
        for(long n=Integer.MAX_VALUE+1;n<=1000000000000L;n+=2){            
boolean flag=true;
            if(isPrime(n)){
                tot+=n;
continue;
            }
            else{
                for(int i=0;i<primi.length;i++){
                    if(n%primi[i]==0){
                        flag=false;
                        tot+=primi[i];
                        break;
                    }
                }
                if(flag) tot+=smpf(n);
            }
        }
        tot=tot%1000000000L;
        System.out.print(tot);


    }
private static boolean isPrimeint(int n) {
        if(n%3 == 0) return false;
        int sqrtN = (int)Math.sqrt(n)+1;
        for(int i = 6; i <= sqrtN; i += 6) {
            if(n%(i-1) == 0 || n%(i+1) == 0) return false;
        }
return true;
    }
private static boolean isPrime(long n) {
        if(n%3 == 0) return false;
        long sqrtN = (long)Math.sqrt(n)+1;
        for(long i = 6L; i <= sqrtN; i += 6) {
            if(n%(i-1) == 0 || n%(i+1) == 0) return false;
        }
return true;
    }

private static int smpfint(int i){
//System.out.println(i);
        int p=99995;
boolean f=true;
        int sqrtI=(int)Math.sqrt(i)+1;
        while(p<sqrtI){
            if(isPrimeint(p)){
                if(i%p==0){
                    return p;
                }
            }
            if(f) {p=p+2;}
            else{ p=p+4;}
            f=!f;
        }
return i;
    }
private static long smpf(long i){
//System.out.println(i);
boolean f=true;
        long p=99995;
        long sqrtI=(long)Math.sqrt(i)+1;
        while(p<sqrtI){
            if(isPrime(p)){
                if(i%p==0){
                    return p;
                }
            }
            if(f) p+=2;
            else p+=4;
            f=!f;
        }
return i;
    }
}