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