Ricerca numeri primi

[SkZ]

effettivamente dati $ ~n $ numeri $ ~a_i $ esistono infiniti polinomi di grado $ ~n $ che passano per i punti $ ~(k,a_k) $
un po' dura scegliere il successivo.
Una sequenza casuale e' quella ottenuta basandosi su processi fisici noti per essere casuali, come fenomeni quantistici & similia (v. generatore hardware di numeri casuali)

[rand]

Una definizione di sequenza casuale è quella di Kolmogorov: fissato un linguaggio di programmazione di riferimento, si dice casuale una sequenza che non può essere generata da un programma più corto della sequenza stessa.

Se la adottiamo allora curiosamente (questo è relativo...) i primi da 1 a N, per N abbastanza grande, non sono una sequenza casuale, perchè sappiamo scrivere una procedura di lunghezza C + log N, dove C è costante dipendente solo dal linguaggio e log N è la lunghezza del contatore, che genera i primi da 1 a N, ed essendoci circa N/logN primi nella sequenza questa diverrà inevitabilmente più lunga del programma al crescere di N.

[thenigma]

Per trovare tutti i primi da 1 ad n basta applicare il crivello di eratostene (sempre che non si abbiano particolari esigenze computazionali).
Una veloce (e senza alcuna pretesa) implementazione in matlab è:

Codice: Seleziona tutto

n = input('inserisci il numero di partenza ');

L = [0, 2 : n];

for i = 2 : sqrt(n)

  for j = 1 : n-i

    if ( mod(L(1,i+j), i) == 0 )
    L(1,i+j)=0;
    end

  end

end

for i=1:n

  if L(1,i) ~= 0
  disp(L(1,i));
  end

end

In C è la stessa cosa (si usa l'operatore %), la traduzione è davvero molto vicina (ma non ho idea di quale sia il linguaggio richiesto quindi me la risparmio ).

[giorgiobusoni87]

allora, partecipo alla discussione dato che è un problema che styo' riaffrontando in questi giorni...avevo un buon programma ma ho perso il codice, adesso ne sto riscrivendo uno e cercando di renderlo efficace.
Il primo metodo che mi è venuto in mente è stato spiegato subito, chè creare un array e infilarci i primi uno dietro l'altro, e per trovare altri primi usare i primi a nostra disposizione nell'array. Ottimizzazioni aggiunte: controlla fino a sert(x) e salta i numeri pari.
Tuttavia usando un array normale in C non sono riuscito ad andare oltre 150000 numeri primi (se creo array più grossi crasha). Allora ho fatto una cosa così:

Codice: Seleziona tutto

#include "numerip.h"
#include <stdio>
#include <vector>
#include <malloc>
#include <algorithm>
using namespace std;
vector<unsigned> numerip;
vector<unsigned>::iterator it;

void main()
{
            unsigned long long int i=1, n, j, r;
//			struct elemento *lista = NULL;
			bool primo;
//			unsigned long int numerip[250000]={2, 3};
            printf("Inserisci l'estremo superiore dell'intervallo\n");
            scanf("%llu", &n);
			numerip.resize(n);
			numerip[0]=2;
			numerip[1]=3;
            j=5;         
			/* dichiara lo stream e il prototipo della funzione fopen */
			FILE * stream; 
			/* apre lo stream del file */
			stream = fopen("primi.txt", "w");
			/* controlla se il file viene aperto */
			if ((stream = fopen("primi.txt", "w")) == NULL)
			{
				printf("Non posso aprire il file %sn", "primi.txt");
			}
			fprintf(stream, "%llu, ", numerip[0]);
			fprintf(stream, "%llu, ", numerip[1]);
            while (j<n>=numerip[h]*numerip[h]) {
                    r=j%numerip[h];
                    if(r==0) {
                        primo=false;
                        break;
                        }
                    h++;
                    }
                if(primo==true) {
                    i++;
                    numerip[i]=j;
					fprintf(stream, "%llu, ", numerip[i]);
                    }
                j=j+2;
                }
			printf("Ho trovato %d numeri\n", i);
			}

Questa funziona tranquillamente fino a p<100000000 sul mio pc (credo dipenda dalla ram, per calcolarne i primi <100000000 ne cosumanva 700MB). Da questo ho dedotto che un programma così è fortemente limitato....certo, con i primi <100000000 potrei calcolarli fino a 100000000^2 ma ci ha messo quasi 20 minuti a farne 100000000).
Pensavo allora di usare il crivello di eratostene. Andrea M. ha sviluppato questo programma allora:

Codice: Seleziona tutto

#include <stdio>
#include <vector>
#include <algorithm>
using namespace std;
unsigned long long int N;
vector<bool> V;
vector<bool>::iterator it;
int
main()
{
FILE *fw;
fw=fopen("output.txt","w");
if(fw==NULL){printf("ERROR while opening output.txt\n");return 1;}
printf("Inserisci N\n");
scanf("%llu",&N);
V.resize(N);//settati tutti a 0: 0 se è primo 1 se no
for(unsigned long long int i=2;i<N;i++)
   {
    if(!V[i])
       for(unsigned long long int j=2 ;i*j<N;j++)
        V[i*j]=true;
   }   
//STAMPA
for(unsigned long long int i=2;i<N;i++)
   if(!V[i])fprintf(fw,"%llu ",i);

return 0;
}

A lui su linux va molto veloce, ma a me su windows va estremamente lento (più dell'altro, per esempio per calcolare i primi <3000000 il mio ci mette sui 5 secondi, il suo (sul mio pc) 80 secondi, sul suo pc 2 secondi. Ancora non abbiamo capito perchè. A qualcuno viene in mente un metodo più veloce (non solo a livello di algoritmo matematico, ma anche si programma in C)?

[MindFlyer]

Beh, un'ottimizzazione ovvia di quel crivello di Eratostene "pecorone" è:
trovato un primo p, inizia a crivellare da p*p, e non da 2p.

E poi, For Fuck's Sake, non fate tutte quelle moltiplicazioni!!!
Fare j++ e poi calcolare i*j ad ogni ciclo, con i che resta costante, è da fessi, scusatemi...

[mykelyk]

Gli ho dato una buona ottimizzazione, che ne pensate?
N = 1000000000 Sul mio computer l'ho portato a 1 secondo di uso cpu
Meglio di così cosa c'è?

Codice: Seleziona tutto

#include "stdafx.h"
int main(){
	__w64 unsigned int t, i, j;
	bool* V = new bool[1000000000];
	V[0] = V[1] = false;
	for(j=4; j<1000000000; j+=2)
		V[j] = false;
	for(i=3; i<1000000000; i+=2)
		if(V[i])
			for(j=i*i, t=2*i; j<1000000000; j+=t)
				V[j] = false;
	//FILE *fw = fopen("output.txt", "w");
	//fprintf(fw, "%i\n", 2);
	//for(i=3; i<1000000000; i+=2)
	//	if(V[i])
	//		fprintf(fw,"%i\n",i);
	return 0;
}

[fph]

La ditta consiglia:

Codice: Seleziona tutto

#define N 1000000000

[Reese]

Così ha anche senso l'array dinamico, dato che prima sarebbe stato meglio dichiararlo normalmente.

[mykelyk]

L'array è dinamico perché è troppo grosso 1000000000 bool tengono circa un giga di ram, troppo per essere dichiarato normalmente.

Codice: Seleziona tutto

#define N 1000000000

Non mi funziona, non ho la più vaga idea del perchè.
Potrei naturalmente inserire una nuova variabile N = 1000000000, ma l'algoritmo sarebbe più lento.

[SkZ]

si puo' cercare di eliminare i pari, ricordando che il primo pari e' ovviamente primo
in modo che V mi dia indicazioni su $ ~2i+1 $
(soprattutto dato che tu gia' stampi il 2 come primo a priori del valore in V[2])

Codice: Seleziona tutto

#include "stdafx.h"
int main(){
	__w64 unsigned int t, i, j;
	bool* V = new bool[1000000000];
	V[0] = false;	
	for(i=1; i<1000000000; i++)
		if(V[i])
			for(j=i*(i+1)<<1, t=2*i+1; j<1000000000; V[j+=t] = false);				
	//FILE *fw = fopen("output.txt", "w");
	//fprintf(fw, "%i\n", 2);
	//for(i=1; i<1000000000; i++)
	//	if(V[i])
	//		fprintf(fw,"%i\n",2*i+1);
	return 0;
}

[mykelyk]

@SkZ: Ci stavo già pensando ieri, ed oggi l'ho fatto:

Ora i pari vengono saltati e V da indicazioni su 2i +1 esattamente come diceva SkZ:

Codice: Seleziona tutto

#include "stdafx.h"
#include <iostream>
#include <math>
using namespace std;
int main(){
	#define			   MAX			   2000000000
	__w64 unsigned int t, i, j,
					   HALFMAX		= (MAX+1)/2,
					   RADMAX		= (int)sqrt((long double)MAX)+1,
					   HALFRADMAX	= (RADMAX+1)/2;
	bool* V = new bool[HALFMAX];
	V[0] = false;
	for(i=1; i<HALFMAX; i++)
		V[i] = true;
	for(i=1; i<HALFRADMAX; i++)
		if(V[i]) 
			for(j= i*(t=2*i+2), t--; j<HALFMAX; j+=t)
				V[j] = false;
	//FILE *fw;
	//fopen_s(&fw, "output.txt", "w");
	//fprintf(fw, "%i\n", 2);
	//for(i=1; i<HALFMAX; i++)
	//	if(V[i])
	//		fprintf(fw,"%i\n",2*i+1);
	cout << 2 << endl;
	for(i=j=1; i<HALFMAX; i++){
		if(!V[i])
			continue;
		cout << 2*i+1;
		if(++j%20)
			cout << endl;
		else{
			char pause[2];
			cin.getline(pause, 1);
		}
	}	
	cout << ">- Finito -<" << endl;
	char pause[2];
	cin.getline(pause, 1);
	return 0;
}

Tempo sul mio computer(ottimizzato tutto) 44-45 secondi.

Mi è venuta un'idea per aumentare ancora la capacità, provo a metterla in pratica

[mykelyk]

Lascio perdere.
Se qualcuno ha voglia di provarci...

Codice: Seleziona tutto

union bools{
  public:
  unsigned char byte;
  struct bits{
    public:
    unsigned char _0:1, _1:1, _2:1, _3:1, _4:1, _5:1, _6:1, _7:1;
  } bit;
};

//Permette di accedere ai singoli bit.
bools V;
V.byte = 0XFF; // reset
V.bit._3 = 0;

In questo modo si ottiene un risparmio di memoria dell'87,5%
Ma mi sono perso.
Buona notte.

[Reese]

Codice: Seleziona tutto

#define N 1000000000

Non mi funziona, non ho la più vaga idea del perchè.
Potrei naturalmente inserire una nuova variabile N = 1000000000, ma l'algoritmo sarebbe più lento.

Prova

Codice: Seleziona tutto

const int N = 1000000000;

.

[SkZ]

l'effetto e' diverso:
col define la sostituzione viene fatto dal preprocessore, quindi al momento della compilazione, mentre definendo la variabile la sostituzione viene al momento dell'esecuzione con accesso alla memoria



hai controllato che il tuo sistema non usi gia' 1bit per i bool?

[Reese]

l'effetto e' diverso:
col define la sostituzione viene fatto dal preprocessore, quindi al momento della compilazione, mentre definendo la variabile la sostituzione viene al momento dell'esecuzione con accesso alla memoria



hai controllato che il tuo sistema non usi gia' 1bit per i bool?

Ti riferisci al const N = ... ?

Mi sa che e' la stessa cosa di define..