Ecco il codice!

Di seguito il programmino promesso. Lo so: sarebbero possibili tantissime ottimizzazioni ma ho preferito scrivere il codice in maniera più chiara possibile...
Sfortunatamente non è molto leggibile perché la formattazione è andata persa (mesi fa ho disabilitato, per problemi con la piattaforma blogger.com, l'estensione che mi permetteva di visualizzare in maniera carina il codice...)
Sicuramente, al di là dei principi matematici, le funzioni calcolaN() e calcolaI() andrebbero riscritte decentemente affinché: 1) non ci siano limitazioni arbitrarie di esponenti 2) I sia mantenuto il più piccolo possibile (giocando con i logaritmi naturali avevo trovato come fare ma il codice mi veniva troppo complicato!)

In pratica il codice è composto da due cicli: il ciclo esterno, partendo da un insieme (senza buchi!) di numeri primi (anche i soli 2 e 3 sono sufficienti), calcola i due insiemi Basso e Alto. Nel ciclo interno, usando i primi degli insiemi Basso e Alto, vengono calcolati altri numeri primi; alla fine di questo ciclo (estremamente arbitrario!) i tre numeri primi più piccoli trovati vengono aggiunti all'insieme iniziale: questo è il passaggio critico perché se viene “dimenticato” un numero primo più piccolo di quelli aggiunti si ha il problema che, alle iterazioni successive, vengano calcolati come primi numeri che in effetti sono il prodotto dei primi “dimenticati”...

Modificato 2/5/2013 ore 1:09AM: non ho fatto in tempo a spegnere la luce per dormire che mi sono reso conto di un errore nel codice! Mi ero dimenticato di controllare che i K trovati non fossero maggiori del quadrato del primo più grande nell'insieme Alto... La seguente versione del codice è stata corretta.


package base;

import java.math.BigInteger;
import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;

public class Crivello
{
ArrayList<BigInteger> primi;

ArrayList<BigInteger> nprimi;
HashMap<BigInteger,Boolean> mappaPrimi;

ArrayList<BigInteger> basso;
ArrayList<BigInteger> alto;

BigInteger quadrato;

int I=0;
int N=0;

public static void main(String[] args)
{
Crivello c=new Crivello();
c.execute();
}

private void execute()
{
/* Inizializza le variabili globali e la lista iniziale di numeri primi */
init();
/* Ciclo esterno arbitrariamente scelto di 10 iterazioni */
for(int est=0;est<10;est++)
{
/* Separo i due insiemi Basso e Alto*/
trovaBassoAlto();
int combBasso=0, combAlto=0;
boolean primaIte=true;
BigInteger oldK1=null, oldK2=null;
/* Ciclo interno arbitrariamente scelto di 1000 iterazioni*/
for(int cc=0;cc<1000;cc++)
{
/* Calcola I e N */
BigInteger I=calcolaI(combBasso);
BigInteger N=calcolaN(combAlto);
//System.out.println("I="+I+ " N="+N);
/* Calcola i candidati primi K1 e K2*/
BigInteger k1=N.mod(I);
BigInteger k2=I.subtract(k1);
/* Memorizza i valori di K1 e K2 alla prima iterazione*/
if(primaIte)
{
primaIte=false;
oldK1=new BigInteger(k1.toString());
oldK2=new BigInteger(k2.toString());
}
/* Se K1 era già stato provato allora non ha più senso calcolare nuovi N e quindi si cambia I (ripartendo con esponenti=1 per N) */
else if(k1.equals(oldK1)||k1.equals(oldK2))
{
primaIte=true;
combBasso++;
combAlto=0;
continue;
}
/* Si verifica che K1 o K2 non siano divisibili per nessun primo in Alto */
k1=controllaAlto(k1);
k2=controllaAlto(k2);
/* Si memorizzano i K trovati se sono primi mai trovati prima */
if(!mappaPrimi.containsKey(k1) && !k1.equals(BigInteger.ONE))
{
nprimi.add(k1);
mappaPrimi.put(k1, true);
}
if(!mappaPrimi.containsKey(k2) && !k2.equals(BigInteger.ONE))
{
nprimi.add(k2);
mappaPrimi.put(k2, true);
}
//System.out.println("k1="+k1+" k2="+k2);
/* Alla prossima iterazione si calcolerà un nuovo N lasciando invariato I*/
combAlto++;
}
Collections.sort(nprimi);
/* Si aggiungono all'insieme di primi iniziale i tre numeri primi più piccoli trovati Il pericolo è quello di "dimenticare" dei numeri primi più piccoli di quelli aggiunti: se così avviene, alle iterazioni successive, potrebbero essere restituiti come primi numeri prodotti dei primi "dimenticati".
Per minimizzare questo rischio mi limito ad aggiungere solo tre numeri primi a ogni iterazione esterna */
primi.add(nprimi.remove(0));
primi.add(nprimi.remove(0));
primi.add(nprimi.remove(0));
}
/* Si stampano i risultati*/
System.out.println("Numeri Primi trovati: "+nprimi.size());
System.out.println("Usati come base:");
for(BigInteger bi : primi)
System.out.println(bi);
System.out.println("Altri numeri primi:");
for(BigInteger bi : nprimi)
System.out.println(bi);
}

/* Si divide il candidato primo per i primi dell'insieme Alto e si restituisce BigInteger.ONE se risulta non primo.
Controlla anche che il numero trovato non sia più alto del quadrato del primo più grande nell'insieme Alto */
private BigInteger controllaAlto(BigInteger primo)
{
if(primo.compareTo(quadrato)>0)
return BigInteger.ONE;
boolean flag=false;
for(BigInteger bi : alto)
if(primo.mod(bi).equals(BigInteger.ZERO))
{
flag=true;
break;
}
if(flag)
return BigInteger.ONE;
else
return primo;
}

/* Si scelgono l'insieme basso e alto facendo in modo che il prodotto dei primi dell'insieme Basso sia minore del quadrato del primo più grande dell'insieme Alto */
private void trovaBassoAlto()
{
basso.clear();
alto.clear();
Collections.sort(primi);
BigInteger quad=primi.get(primi.size()-1);
quad=quad.multiply(quad);
int ele=0;
BigInteger soglia=BigInteger.ONE;
while(soglia.compareTo(quad)<0 && ele<primi.size()-1)
{
soglia=soglia.multiply(primi.get(ele++));
}
for(int i=0;i<ele;i++)
basso.add(primi.get(i));
for(int i=ele;i<primi.size();i++)
alto.add(primi.get(i));
quadrato=alto.get(alto.size()-1).pow(2);
}

/* Funzione di utilità usata da calcolaN e calcolaI */
/* Sono consapevole che la tecnica che ho usato per determinare gli esponenti è buggata! Gli esponenti non possono superare il limite che ho arbitrariamente imposto: ovvero 35 per un solo elemento, 20 per due e 12 negli altri casi! Quando questo limite viene superato l'esponente torna a 1 facendo così ritrovare dei K1 e K2 già trovati: a sua volta questo innesca un cambiamento di I...*/
private String faiStringa(int comb, int ele)
{
String s;
int radice=12;
if(ele==1)
radice=35;
if(ele==2)
radice=20;
s=Integer.toString(comb, radice);
while(s.length()<ele)
s+="0";
return s;
}

private BigInteger calcolaN(int comb)
{
String esp=faiStringa(comb,alto.size());
BigInteger val=BigInteger.ONE;
for(int i=0; i<alto.size();i++)
{
int potenza=(esp.charAt(i)<='9'?esp.charAt(i)-'0'+1:esp.charAt(i)-'a'+11);
val=val.multiply(alto.get(i).pow(potenza));
}
return val;
}

/* Idealmente bisognerebbe scegliere gli esponenti in maniera che I cresca il minimo possibile: in questa maniera si massimizzerebbero le iterazioni utili */
private BigInteger calcolaI(int comb)
{
String esp=faiStringa(comb,basso.size());
BigInteger val=BigInteger.ONE;
for(int i=0; i<basso.size();i++)
{
int potenza=(esp.charAt(i)<='9'?esp.charAt(i)-'0'+1:esp.charAt(i)-'a'+11);
val=val.multiply(basso.get(i).pow(potenza));
}
return val;
}

/* Qualche inizializzazione... */
private void init()
{
int[] seeds={2,3,5,7}; //,11,13,17,19,23,29,31};
basso=new ArrayList<BigInteger>();
alto=new ArrayList<BigInteger>();
primi=new ArrayList<BigInteger>();
nprimi=new ArrayList<BigInteger>();
mappaPrimi=new HashMap<BigInteger,Boolean>();
for(int n : seeds)
{
primi.add(new BigInteger(Integer.toString(n)));
}
}

}

Share