IALweb Homepage
Forum Home Forum Home > Programmazione > Programmazione > JAVA
  New Posts New Posts RSS Feed - Numeri Primi
  FAQ FAQ  Forum Search   Events   Register Register  Login Login

REGISTRATEVI su IALWeb forum! E' facile e veloce! Potrete consultare tutte le sezioni del forum senza restrizioni e scrivere per dare o richiedere aiuto.
Votaci in Net-Parade

Numeri Primi

 Post Reply Post Reply
Author
Message
Platform View Drop Down
Utente Senior
Utente Senior
Avatar

Joined: 20/Set/2017
Location: Italy
Status: Offline
Points: 285
Post Options Post Options   Thanks (0) Thanks(0)   Quote Platform Quote  Post ReplyReply Direct Link To This Post Topic: Numeri Primi
    Posted: 09/Ott/2017 at 10:12
Ho fatto un programma sui numeri primi molto più veloce del normale per il momento il codice è top secret livello calamità Demone lol
https://www.youtube.com/watch?v=c_HE36imS0E


Edited by Platform - 09/Ott/2017 at 14:23
Back to Top
willy55 View Drop Down
Moderatore
Moderatore
Avatar
Esperto di Access

Joined: 03/Ago/2011
Location: Italy
Status: Offline
Points: 8881
Post Options Post Options   Thanks (0) Thanks(0)   Quote willy55 Quote  Post ReplyReply Direct Link To This Post Posted: 10/Ott/2017 at 00:52
Willy
Back to Top
Platform View Drop Down
Utente Senior
Utente Senior
Avatar

Joined: 20/Set/2017
Location: Italy
Status: Offline
Points: 285
Post Options Post Options   Thanks (0) Thanks(0)   Quote Platform Quote  Post ReplyReply Direct Link To This Post Posted: 10/Ott/2017 at 08:33
Originally posted by willy55 willy55 wrote:

Un programma sui numeri primi deve avere una solida base matematica in quanto possono esistere diversi algoritmi che cercano di risolvere i vincoli conosciuti:
http://www.dsi.unive.it/~focardi/corso-security/progetti0809/slides-bergamasco.pdf
http://matematica.unibocconi.it/articoli/numeri-primi-e-complessit%C3%A0lalgoritmo-aks
http://www.lescienze.it/news/2016/09/30/news/nuovo_metodo_calcolare_numeri_computer-3251946/
https://www.galileonet.it/2013/05/i-numeri-primi-vanno-in-coppia/

comunque per valutare gli aspetti di velocità è basilare determinare la complessità computazionale, applicabile a quanto realizzato:
https://it.wikipedia.org/wiki/Test_di_primalit%C3%A0#Complessit.C3.A0_computazionale
http://amslaurea.unibo.it/6345/
http://utenti.quipo.it/base5/ricevuto/tesistocchi.htm


Grazie per i link così posso valutare la situazione Smile. Nei prossimi giorni posto qua il codice (anche se nel video ero titubante a fare ciò) per avere un parere.
Back to Top
Platform View Drop Down
Utente Senior
Utente Senior
Avatar

Joined: 20/Set/2017
Location: Italy
Status: Offline
Points: 285
Post Options Post Options   Thanks (0) Thanks(0)   Quote Platform Quote  Post ReplyReply Direct Link To This Post Posted: 14/Ott/2017 at 11:33
Originally posted by willy55 willy55 wrote:

Un programma sui numeri primi deve avere una solida base matematica in quanto possono esistere diversi algoritmi che cercano di risolvere i vincoli conosciuti:
http://www.dsi.unive.it/~focardi/corso-security/progetti0809/slides-bergamasco.pdf
http://matematica.unibocconi.it/articoli/numeri-primi-e-complessit%C3%A0lalgoritmo-aks
http://www.lescienze.it/news/2016/09/30/news/nuovo_metodo_calcolare_numeri_computer-3251946/
https://www.galileonet.it/2013/05/i-numeri-primi-vanno-in-coppia/

comunque per valutare gli aspetti di velocità è basilare determinare la complessità computazionale, applicabile a quanto realizzato:
https://it.wikipedia.org/wiki/Test_di_primalit%C3%A0#Complessit.C3.A0_computazionale
http://amslaurea.unibo.it/6345/
http://utenti.quipo.it/base5/ricevuto/tesistocchi.htm

Allora l'algoritmo si chiama Qu5 il codice è diviso in queste due parti:
Programma Qu3
/**
 * @(#)Qu3.java
  Riccardo Munaro 
 * @version 1.00 2013/4/12
 */
interface Qu3_{
//azzera i numeri non primi sulla sequenza 1
public void sequenza1(int n);
//azzera i numeri non primi sulla sequenza 2
public void sequenza2(int n);
//Restituisce un numero primo nella posizione i della sequenza 1
public int primiSeq1(int i);
//Restituisce un numero primo nella posizione i della sequenza 2
public int primiSeq2(int i);
//Restituisce quantità di operazioni
public int operation();
}

class Qu3 implements Qu3_ {
private int [] a;//sequenza 1 
private int [] b;//sequenza 2 
private int n;//numeri totali delle due sequenze
private int u=0;//calcolo operazioni
//Costruttore delle due sequenze
public Qu3(int n){
this.a=new int [n/2];//creazione sequenza 1
this.b=new int [n/2];//creazione sequenza 2
this.a[0]=5;//primo elemento della sequenza 1
this.b[0]=7;//primo ellemento della sequenza 2
int i=1;//a partire dal secondo numero
//creazione degli i-esimi elementi per entrambe le sequenze
while(i<n/2){
this.a=b[i-1]+a[0]-1;
this.b=a+2;
i++;
}
}
//azzera i numeri non primi sulla sequenza 1
public void sequenza1(int n){
int i;
int s=0,x,d;
//condizione per controllare tutti i numeri
//ricerca diretta
while(s<n/2){
//x assume il valore dell'elemento con chiave s
x=this.a[s];
if(x>0)
//se il numero era stato azzerato non viene preso in considerazione
//parte dal primo numero da azzerare
for(i=s+x;i<n/2;i=i+x){
this.a=0;
u=u+1;
}
//azzera i multipli del numero alla posizione s
s++;
}
}
//azzera i numeri non primi sulla sequenza 2
public void sequenza2(int n){
int i;
int s=0,x,d;
while(s<n/2){
//condizione per controllare tutti i numeri
//ricerca diretta
x=this.b[s];
//x assume il valore dell'elemento con chiave s
//se il numero era stato azzerato non viene preso in considerazione
if(x>0)
//parte dal primo numero da azzerare
for(i=s+x;i<n/2;i=i+x){
//azzera i multipli del numero alla posizione s
this.b=0;
u=u+1;
}
//ricerca a ritroso
//parte dal primo elemento da azzerare
d=this.a[s]-2-s;
//x assume il valore dell'elemento con chiave s
x=this.a[s];
//se il numero era stato azzerato non viene preso in considerazione
if(x>0)
//parte dal primo numero da azzerare
for(i=d;i<n/2;i=i+x){
//azzera i multipli del numero alla posizione s
this.b=0;
u=u+1;
}
s++;
}
}
//Restituisce un numero primo nella posizione i della sequenza 1
public int primiSeq1(int i){
return this.a;
}
//Restituisce un numero primo nella posizione i della sequenza 2
public int primiSeq2(int i){
return this.b;
}
//Restituisce quantità di operazioni
public int operation(){
return u;
}
}

class UsaQu3{
public static void main(String[] args){
int n=100;
Qu3 q=new Qu3(n);
q.sequenza1(n);
q.sequenza2(n);
int i,j=2;
//Comunicazione dei numeri primi
System.out.println("Numeri Primi:");
System.out.println("2\n3");
for(i=0;i<n/2;i++){
if(q.primiSeq1(i)!=0){
System.out.println(""+q.primiSeq1(i));
j++;
}
if(q.primiSeq2(i)!=0){
System.out.println(""+q.primiSeq2(i));
j++;
}
}
}
}
Programma Qu5:
/**
 * @(#)Qu5.java
  Creator: Riccardo Munaro
 * @version 1.5 2013/4/14
 */
import java.util.Scanner;

interface Qu5_{
//Comunica i numeri compresi tra r e s
public void primi(int r,int s);
//Comunica tutti i numeri primi della sequenza dei numeri primi
public void allPrimi();
//Restituisce il valore del massimo nuermo primo contenuto
public int max();
//Restituisce quantità di numeri trovati in un intervallo
public int inv();
//Restituisce quantità di numeri primi
public int spac();
//restituisce l'array dei numeri primi
public int[] prime();
//seleziona un numero dell'array
public int select(int [] c, int key);
}
class Qu5 implements Qu5_ {
//dimensione della sequenza contenente i numeri primi
private int n;
//sequenza dei numeri primi
private int [] c;
private int k=0;
private int a=0;
//crea un oggetto contenente numeri primi
    public Qu5(int p) {
int n=p;
long startTime = System.currentTimeMillis();
//crea le due sequenze numeriche
Qu3 q=new Qu3(n);
//azzera i numeri non primi della sequenza 1
q.sequenza1(n);
//azzera i numeri non primi della sequenza 2
q.sequenza2(n);
System.out.println("Operazioni: "+q.operation());
int i,j=2;
//calcolo della quantità di posizione per la sequenza contenente i numeri primi
for(i=0;i<n/2;i++){
if(q.primiSeq1(i)!=0){
j++;
}
if(q.primiSeq2(i)!=0){
j++;
}
}
this.n=j;
//sequenza dei numeri primi
this.c=new int [j];
c[0]=2;
c[1]=3;
int v=2;
//immisione dei numeri diversi da zero
for(i=0;i<n/2;i++){
if(q.primiSeq1(i)!=0){
c[v]=q.primiSeq1(i);
v++;
a++;
}
if(q.primiSeq2(i)!=0){
c[v]=q.primiSeq2(i);
v++;
a++;
}
}
prime();
System.out.println("Quantità di numeri su cui è stato eseguito il calcolo:"+n+"\n");
System.out.println("Quantità di numeri primi trovati:"+a+"\n");
spac();
System.out.println("Quantità di numeri composti trovati:"+(n-a)+"\n");
//quantità di numeri primi
float b=a;
//quantità di numeri su cui si sta cercando
float c=n;
//numeri utilizzati in percentuale
float f=(b/c)*100;
System.out.println("Percentuale dei numeri su cui sono stati eseguiti i calcoli:"+f+"\n");
long endTime = System.currentTimeMillis();
long seconds = (endTime - startTime) / 1000;
System.out.println("Programma eseguito in " + seconds + " secondi");
    } 
    //Comunica i numeri compresi tra r e s
public void primi(int r,int s){
int i=0;
//ricerca del numero da cui partire in base al valore r comunicato
while(i<this.n){
if(this.c>=r){
r=i;
i=this.n;
}
i++;
}
i=this.n;
//ricerca del valore su cui terminare in base al valore s comunicato
while(i>0){
if(this.c[i-1]<=s){
s=i;
i=0;
}
i--;
}
this.k=(s-r);
while(r<s){
System.out.println(""+this.c[r]);
r++;
}
}
//Restituisce il valore del massimo numermo primo contenuto
public int max(){
return this.c[this.n-1];
}
//Comunica tutti i numeri primi della sequenza dei numeri primi
public void allPrimi(){
for(int i=0;i<this.n;i++)
System.out.println(""+c);
}
//Restituisce quantità di numeri trovati in un intervallo
public int inv(){
return this.k;
}
//Restituisce quantità di numeri primi
public int spac(){
return a;
}
//restituisce l'array dei numeri primi
public int[] prime(){
return c;
}
//seleziona un numero dell'array
public int select(int [] c, int key){
return c[key];
}
    
}
class UsaQu5{
public static void main(String  args []){
int p;
Scanner seq= new Scanner(System.in);
System.out.println("Inserisci quantità");
p=seq.nextInt();
Qu5 q=new Qu5(p);
int r,s;
int dataSize = 1024 * 1024;
    Runtime runtime = Runtime.getRuntime();
System.out.println ("Memoria Massima: " + runtime.maxMemory() / dataSize + "MB");
    System.out.println ("Memoria Totale: " + runtime.totalMemory() / dataSize + "MB");
    System.out.println ("Memoria Libera: " + runtime.freeMemory() / dataSize + "MB");
System.out.println ("Memoria Usata: " + (runtime.totalMemory() - runtime.freeMemory()) / dataSize + "MB");
int t=1;
while(t==1){
System.out.println("Numero primo massimo:"+q.max()+"\n");
System.out.println("Inserisci il numero d'inizio");
r=seq.nextInt();
System.out.println("Inserisci il numero finale");
s=seq.nextInt();
System.out.println("\nNumeri primi da "+r+" a "+s+":");
q.primi(r,s);
System.out.println("Numeri primi presenti in tale intervallo:"+q.inv());
System.out.println("Cercare altro?SI(1)NO(0)");
t=seq.nextInt();
}
}
}
Gli ho fatto fare il calcolo delle operazioni sulla ricerca di 8 numeri mi fa' un'operazione di azzeramento ursando il 5.
In questo caso creo due sequenze 
Sequenza B:7,13,19,25
Sequenza A:5,11,17,23
Avviene solo l'azzeramento del 25.
Il 2 e il 3 li metto di default.



Edited by Platform - 14/Ott/2017 at 12:14
Back to Top
Platform View Drop Down
Utente Senior
Utente Senior
Avatar

Joined: 20/Set/2017
Location: Italy
Status: Offline
Points: 285
Post Options Post Options   Thanks (0) Thanks(0)   Quote Platform Quote  Post ReplyReply Direct Link To This Post Posted: 14/Ott/2017 at 12:08
Sul CMD:
comandi:
Javac Qu3.java
javac Qu5.java
Java -Xms0m -Xmx9000m UsaQu5
Il problema è che calcola i numeri fino a 2 miliardi e dovrei modificare il programma usando la classe BigInteger al posto del tipo primitivo int.


Edited by Platform - 14/Ott/2017 at 12:15
Back to Top
Platform View Drop Down
Utente Senior
Utente Senior
Avatar

Joined: 20/Set/2017
Location: Italy
Status: Offline
Points: 285
Post Options Post Options   Thanks (0) Thanks(0)   Quote Platform Quote  Post ReplyReply Direct Link To This Post Posted: 14/Ott/2017 at 12:16
Fare questo programma è stato un lavoro molto arduo Ouch
Back to Top
Platform View Drop Down
Utente Senior
Utente Senior
Avatar

Joined: 20/Set/2017
Location: Italy
Status: Offline
Points: 285
Post Options Post Options   Thanks (0) Thanks(0)   Quote Platform Quote  Post ReplyReply Direct Link To This Post Posted: 14/Ott/2017 at 12:20
Back to Top
Platform View Drop Down
Utente Senior
Utente Senior
Avatar

Joined: 20/Set/2017
Location: Italy
Status: Offline
Points: 285
Post Options Post Options   Thanks (0) Thanks(0)   Quote Platform Quote  Post ReplyReply Direct Link To This Post Posted: 15/Ott/2017 at 23:11
Originally posted by willy55 willy55 wrote:

Un programma sui numeri primi deve avere una solida base matematica in quanto possono esistere diversi algoritmi che cercano di risolvere i vincoli conosciuti:
http://www.dsi.unive.it/~focardi/corso-security/progetti0809/slides-bergamasco.pdf
http://matematica.unibocconi.it/articoli/numeri-primi-e-complessit%C3%A0lalgoritmo-aks
http://www.lescienze.it/news/2016/09/30/news/nuovo_metodo_calcolare_numeri_computer-3251946/
https://www.galileonet.it/2013/05/i-numeri-primi-vanno-in-coppia/

comunque per valutare gli aspetti di velocità è basilare determinare la complessità computazionale, applicabile a quanto realizzato:
https://it.wikipedia.org/wiki/Test_di_primalit%C3%A0#Complessit.C3.A0_computazionale
http://amslaurea.unibo.it/6345/
http://utenti.quipo.it/base5/ricevuto/tesistocchi.htm

Questo è il link per vedere come funziona il mio algoritmo 
Back to Top
Platform View Drop Down
Utente Senior
Utente Senior
Avatar

Joined: 20/Set/2017
Location: Italy
Status: Offline
Points: 285
Post Options Post Options   Thanks (0) Thanks(0)   Quote Platform Quote  Post ReplyReply Direct Link To This Post Posted: 20/Ott/2017 at 15:40
Originally posted by willy55 willy55 wrote:

Un programma sui numeri primi deve avere una solida base matematica in quanto possono esistere diversi algoritmi che cercano di risolvere i vincoli conosciuti:
http://www.dsi.unive.it/~focardi/corso-security/progetti0809/slides-bergamasco.pdf
http://matematica.unibocconi.it/articoli/numeri-primi-e-complessit%C3%A0lalgoritmo-aks
http://www.lescienze.it/news/2016/09/30/news/nuovo_metodo_calcolare_numeri_computer-3251946/
https://www.galileonet.it/2013/05/i-numeri-primi-vanno-in-coppia/

comunque per valutare gli aspetti di velocità è basilare determinare la complessità computazionale, applicabile a quanto realizzato:
https://it.wikipedia.org/wiki/Test_di_primalit%C3%A0#Complessit.C3.A0_computazionale
http://amslaurea.unibo.it/6345/
http://utenti.quipo.it/base5/ricevuto/tesistocchi.htm


Ho guardato i link e la comprensione di ciò mi richiederà molto tempo perchè al momento va aldilà delle mie conoscenze.
Back to Top
 Post Reply Post Reply
  Share Topic   

Forum Jump Forum Permissions View Drop Down

Forum Software by Web Wiz Forums® version 10.17
Copyright ©2001-2013 Web Wiz Ltd.

This page was generated in 0,093 seconds.