Crivello di Eratostene in Java

[Scanca]

Ciao a tutti ,
devo implementare il Crivello di Eratostene in Java per memorizzare i numeri primi da 1 a 8000000000.
Ho pensato di usare la struttura dati BitSet, molto efficiente e veloce per il mio scopo.
Il problema è che non posso andare oltre la rappresentazione dei numeri interi (circa 2000000000) perchè il costruttore di BitSet prende come argomento solo interi.
Avevo pensato di usare i long riscrivendomi la classe BitSet ma non ne trovo beneficio visto che la lunghezza di int e long è la stessa.
Come posso fare a superare il limite?

[WarDuck]

In Java int è a 32 bit, long sono 64 bit.

http://docs.oracle.com/javase/tutori...datatypes.html

Tra l'altro ho scoperto adesso che in Java 8 hanno aggiunto dei metodi per fare il confronto unsigned

[Freaxxx]

http://rosettacode.org/wiki/Sieve_of_Eratosthenes#Java

e comunque il crivello di Eratostene non memorizza nulla, è un algoritmo per la generazione di numeri primi.

[Scanca]

Devo tenere in memoria i numeri primi da 0 a 8000000000 in Java.
Uso per generarli il crivello di Eratostene e li memorizzo con un BitSet.
Quindi il mio programma li deve generare, salvare e dare il numero di quanti sono.
Il problema è che non posso passare un numero più grande di 2000000000 perchè la classe BitSet accetta solo int.
Se dichiaro long x = 8000000000; mi viene segnalato un errore di range, come posso fare?

import java.util.BitSet;

public class BitSetLong {

private BitSet primeset;

public BitSetLong(long n){
this.primeset = new BitSet((int) n);
}

public void set(long fromIndex, long toIndex) {
primeset.set ((int)fromIndex, (int) toIndex);
}

public long nextSetBit(long fromIndex) {
long i = fromIndex;
while(!this.get(i++)) {}
return i-1;
}

public int cardinality() {
return primeset.cardinality();
}

public void set(long i) {
primeset.set((int) i);
}

public void clear(long i) {
primeset.clear((int) i);
}

public boolean get(long i) {
return primeset.get((int) i);
}
}

####################################

import java.io.IOException;

public class Eratostene{

public static void main(String [] args) throws IOException {

long n = 1000000000;
long inizio = System.currentTimeMillis();

System.out.println("Inizio generazione numeri primi");
System.out.println("Attendere...");

// costruisco insieme setPrimi = {2,...,n}

BitSetLong2 setPrimi1 = new BitSetLong2(n);
BitSetLong2 setPrimi2 = new BitSetLong2(n);
setPrimi1.set(2,n);
setPrimi2.set(2,n);

// per ogni k in setPrimi, tolgo da setPrimi i multipli m di k tali che m < k <= n

long i=1;
while (i*i<n) {
i= setPrimi1.nextSetBit(i+1);
for(long k=i*i; k<n; k+=i)
setPrimi1.clear(k);
}
System.out.println("Fine generazione numeri primi");

// in setPrimi sono rimasti solamente i numeri primi p tali che 2 <= p <= n

long fine = System.currentTimeMillis();
System.out.println("I numeri primi generati sono: "+(setPrimi1.cardinality()+1));

long time = (fine-inizio)/1000;
System.out.println(time + " sec");

} // end main
} // end class

[sottovento]

Originariamente inviato da Scanca

Devo tenere in memoria i numeri primi da 0 a 8000000000 in Java.
Uso per generarli il crivello di Eratostene e li memorizzo con un BitSet.
Quindi il mio programma li deve generare, salvare e dare il numero di quanti sono.
Il problema è che non posso passare un numero più grande di 2000000000 perchè la classe BitSet accetta solo int.
Se dichiaro long x = 8000000000; mi viene segnalato un errore di range, come posso fare?
<cut>

Probabilmente ti hanno dato proprio dei limiti cosi' ampi per non permetterti di utilizzare strutture gia' pronte e vedere come te la cavi, soprattutto considerando che vai ad utilizzare una quantita' rilevante di memoria.

Ci sono parecchie soluzioni al problema: utilizzo di singoli bit per rappresentare l'informazione dentro/fuori il crivello (riduce il quantitativo di memoria, ma sembrerebbe ancora troppa, per te), bufferizzare su disco, ecc.

Secondo me, potresti dividere il tuo problema in intervalli piu' piccoli, per esempio parti di un milione (beh, potresti fare anche di piu', e' solo per capirsi).
Cominci considerando l'intervallo 0....999999 ed ottieni la lista dei numeri primi (che non e' lunghissima). Poi vai all'intervallo successivo ed elimini immediatamente i numeri primi gia' trovati, quindi applichi il crivello ai rimanenti, e cosi' via.

Non e' difficile da implementare, no?

Anzi, se poi vuoi rendere l'implementazione piu' eccitante, potresti notare che la fase di eliminazione dei numeri potrebbe essere svolta da piu' thread contemporaneamente. Ciascun thread potrebbe avere una sezione della lista da esaminare per eliminare i multipli.
Potresti implementare quindi un algoritmo per l'eliminazione parallela. Se stai usando Java 7 o successivo, potresti considerare l'uso delle primitive di Fork/Join, fatte appunto per problemi come questo.

Se usi Java 8, potresti tentare un'implementazione con i nuovi parallelStream

[DoctorT]

problema interessante, potresti immaginare un bitset che immagazzina solo i numeri dispari utilizzando la formula (n-1)\2, risparmieresti così metà dello spazio di archiviazione.

facci sapere che soluzione trovi.

[Scanca]

Grazie mille delle risposte.
La soluzione finale sarà non salvarmi nel BitSet i multipli di 2,3,5 in modo da non risparmiare la memoria a monte.
Il problema che ho adesso è che non posso mettere la variabile n=8000000000.

Come posso fare a dividerli in intervalli se non posso superare quel limite?
Questo non riesco a capire

[ingframin]

In python è così, se mi dai qualche minuto provo a farlo anche in Java.
Stiamo parlando di circa 9000 numeri eh...
Il tuo problema con la memoria è che cerchi di generare prima tutti i numeri e poi applicare il crivello, mai n pratica basta applicare il crivello dinamicamente

def eratostene(n):
    buffer = []
    flag = False
    for x in range(2,n):
        flag = False
        if x*x > n:
            break
        for y in buffer:
            if x%y == 0:
                flag = True
                break
        if not flag:
            buffer.append(x)
        
            
    return buffer

print(eratostene(8000000000))

a = input()

[DoctorT]

prova a fare long n = 8000000000L

[ingframin]

Originariamente inviato da DoctorT

prova a fare long n = 8000000000L

Non puoi usare BigInteger? Esiste sin da java 1.2 mi pare...
Sennò devi farti una classettina custom.

[ingframin]

Non mi pare una roba impossibile :P

import java.util.*;
import java.math.BigInteger;

public class Eratostene{

	static LinkedList<BigInteger> buffer = new LinkedList<BigInteger>();
	
	public static void run(BigInteger limit){
		boolean flag = false;
		
		
		for(BigInteger x = new BigInteger("2"); x.compareTo(limit)<0; x=x.add(BigInteger.ONE)){
			
			
			if(x.multiply(x).compareTo(limit) > 0){
				
				break;
				}//x*x > limit
				
			for(BigInteger y:buffer){
				
				if(x.remainder(y).equals(BigInteger.ZERO)){
					flag = true;
					break;
				}//x not prime
				
			}//check
			
			if(!flag){
				buffer.add(x);
			}//if
			flag = false;
		}//ext for
		
		
	}//run method
	
	public static void main(String[] args){
		BigInteger limit = new BigInteger("8000000000");
		run(limit);
		System.out.print(buffer.size());
	
	}
}

[marakid]

Originariamente inviato da ingframin

Non puoi usare BigInteger? Esiste sin da java 1.2 mi pare...
Sennò devi farti una classettina custom.

Non ho Eclipse sottomano, ma ha un Long (con la l minuscola o maiuscola) un numero con 9 cifre gli fa ridere...

...manca sicuramente la L in fondo, quindi per lui quello è un int (max 4MLD circa)

[sottovento]

Originariamente inviato da ingframin

Non mi pare una roba impossibile :P
<Cut>

Manca il crivello. Nel tuo codice (correttissimo!) determini se un numero e' primo provando a dividerlo per i numeri primi precedenti. E' un valido algoritmo ma non e' il crivello di Eratostene

[ingframin]

Originariamente inviato da marakid

Non ho Eclipse sottomano, ma ha un Long (con la l minuscola o maiuscola) un numero con 9 cifre gli fa ridere...

...manca sicuramente la L in fondo, quindi per lui quello è un int (max 4MLD circa)

Hai ragione, è la mia conoscenza di java che è scarsa, lo uso pochissimo, né mi è mai capitato di usare long... Inoltre non in tutti i linguaggi è necessario mettere la L alla fine.

[DoctorT]

comunque il problema, oltre che di codifica riguarda anche la dimensione di memoria, perchè un crivello costituito da 8000000000 di byte occuperebbe circa 8GB di RAM e la soluzione sarebbe fortemente dipendente dall'hardware sul quale faccio girare il programma.

la soluzione comunque c'è: il crivello di eratostene segmentato, vi allego una implementazione in C++

http://primesieve.org/segmented_sieve.html

[ingframin]

Originariamente inviato da sottovento

Manca il crivello. Nel tuo codice (correttissimo!) determini se un numero e' primo provando a dividerlo per i numeri primi precedenti. E' un valido algoritmo ma non e' il crivello di Eratostene

No, il mio codice è esattamente il crivello e ti spiego perché.
Eratostene che il computer non lo aveva si scriveva tutti gli interi a manina e poi, partendo dal primo, li divideva per tutti i precedenti.
Tutti i multipli di quelli di prima venivano scartati e si ripartiva fino a togliere tutti i numeri dal "crivello".
Quello che serve non è un array di numeri ma un sistema per "scriversi"i numeri primi ed eliminare quelli che non servono.
In Java non ho i generators come in Python né posso caricare in memoria 8 miliardi di long (~=64GB di RAM!!!).
Quindi il mio sistema di scrivere gli interi è usare un for.
Siccome il massimo primo della lista al quadrato è minore del limite basta fermare il for a x*x < limit.
Il mio procedimento prende i numeri dell'insieme 2->limit e li divide a uno a uno per i numeri rimasti nel crivello, dopodiché li mette nella lista che rappresenta il risultato finale.
Sicuramente è più contorto ma non c'è nessuna differenza col crivello di eratostene (eccetto che la lista di numeri da crivellare viene generata dinamicamente invece che scritta apriori).

Imparando da DoctorT e marakid:

import java.util.*;

import java.sql.Timestamp;

public class EratosteneLong{

	static LinkedList<Long> buffer = new LinkedList<Long>();
	
	public static void run(Long limit){
		boolean flag = false;
		
		
		for(Long x = 2L; x*x<limit; x++){
			
				
			for(Long y:buffer){
				
				if(x%y==0){
					flag = true;
					break;
				}//x not prime
				
			}//check
			
			if(!flag){
				buffer.add(x);
			}//if
			flag = false;
		}//ext for
		
		
	}//run method
	
	public static void main(String[] args){
		long now = System.currentTimeMillis();
		
		Long limit = 8000000000L;
		run(limit);
		long final_time = System.currentTimeMillis() - now;
		System.out.println("time spent= "+final_time);
		System.out.print(buffer.size());
	
	}
}

Se poi mi sapete anche indicare un sistema per misurare il tempo di esecuzione simile a cProfile di Python mi fate felice
Ho provato questo:
http://docs.oracle.com/javase/7/docs...les/hprof.html
ma non ho capito come funziona

[wingman87]

Sono daccordo con sottovento, non è il crivello.
Ora non ho il tempo di dettagliare, se non ci ha già pensato qualcunaltro scrivo stasera.

[DoctorT]

intanto posto la mia implementazione in java :

import java.util.BitSet;
import java.util.Vector;
import java.lang.Math;
import java.io.*;

class Eratostene{
    
	static int segmented_sieve(long limit, int segment_size) {
		int sqrt = (int) Math.sqrt((double)limit);
		int count = 1;
		long s = 2;
		long n = 3;
		
		BitSet sieve = new BitSet(segment_size);
		// togli il commento se vuoi i numeri stampati a video
		// System.out.println(2);
		System.out.println("sqrt="+ sqrt);
		
		// crea un array di numeri primi < di sqrt(limit)
		
		boolean[] is_prime = new boolean[sqrt+1];
		for (int i=0;i<=sqrt;i++) is_prime[i] = true;
		for (int i = 2; i * i <= sqrt; i++)
		  {
			if (is_prime[i])
				for (int j = i * i; j <= sqrt; j += i)
					is_prime[j] = false;
		}
	
		Vector<Integer> primes = new Vector<Integer> ();
		Vector<Integer> next = new Vector<Integer> ();
		
		for (long low = 0; low <= limit; low += segment_size)
		{
			sieve.set(0, segment_size-1);		
			// current segment = interval [low, high]
			long high = Math.min(low + segment_size - 1,  limit) ;
			// memorizza i primi occorrenti per incrociare i multiple
			for (; s * s <= high; s++)
			{
				if (is_prime[(int)s])
				{
					primes.add((int)s);
					next.add((int)(s * s - low));
				}
			}
		
			// crivello per il segmento corrente
			for (int i = 1; i < primes.size(); i++)
			{
				int j = next.get(i);
				for (int k = primes.get(i) * 2; j < segment_size; j += k)
					sieve.clear(j);
				next.set(i, j - segment_size);
			}

			for (; n <= high; n += 2) // ricerca i bit con indice dispari
				if (sieve.get((int)(n - low))) // n is a prime
				{
					count++;
					// togli il commento se vuoi i numeri stampati a video
					// System.out.println(n); 
				}
		};
		return count;
	}
	
	public static void main(String [] args) throws IOException {	

		int sieve_size = 65536;
		long n = 8000000000L;
		long inizio = System.nanoTime();

		System.out.println("Attendere");	
		System.out.println("generazione numeri primi ..."); 
		System.out.println("I primi generati sono: " + segmented_sieve(n,sieve_size));

		long fine = System.nanoTime();
		float time = (fine-inizio)/1000000;
		System.out.println(time + " ms");

	} // end main
} // end class

il tempo di esecuzione sul mio sistema è di circa 130 secondi ... mi sa che c'è un bel po' da ottimizzare

[ingframin]

Originariamente inviato da wingman87

Sono daccordo con sottovento, non è il crivello.
Ora non ho il tempo di dettagliare, se non ci ha già pensato qualcunaltro scrivo stasera.

Si per favore perché non capisco dove sta la differenza tra il mio metodo e quello di eratostene.

[DoctorT]

ingframin il tuo codice non restituisce il risultato giusto

sostituendo: for(Long x = 2L; x*x<limit; x++)

con: for(Long x = 2L; x<limit; x++)

il risultato è esatto ma la performance è pessima.