[c++ / calcolo numeri primi] - Mi salta il numero 1 !

[unslee]

Ciao a tutti,
ho risolto un esercizio nel quale veniva chiesto di restituire in output tutti i numeri primi da 1 a 100.000.

Per calcolare se un numero è primo ho creato la funzione prime.

Nella prima versione ho filtrato l'elaborazione nella funzione prime escludendo a priori tutti i numeri che modulo 2 restituivano 0.

Nella seconda versione ho filtrato l'elaborazione nella funzione prime escludendo (grazie all'aiuto di Ziosilvio!) tutti i numeri la cui radice quadrata fosse intera.

Per ottimizzare le prestazioni ho creato una versione 3 del programma che nella funzione prime, prima di procedere all'elaborazione, esclude sia tutti i numeri che nodulo 2 restituiscono 0 sia la cui radice quadrata sia intera.

Prima versione: 58 secondi
Seconda versione: 1' e 31 secondi
Terza version: 40 secondi

L'ottimizzazione delle prestazioni c'è stata ma il mistero è che la versione 3 non mi mostra il numero 1 come primo
La cosa strana è che il numero 1 è proprio il primo argomento passato alla funzione prime che, tra l'altro, lo tratta esplicitamente.
Nelle altre 2 versioni il numero 1 viene outputtato.

// Esercizio 630.cpp : definisce il punto di ingresso dell'applicazione console.
//

#include "stdafx.h"

#include <iostream>
using std::cin;
using std::cout;
using std::endl;

#include <cmath>
using std::sqrt;

int _tmain(int argc, _TCHAR* argv[])
{
	return 0;
}

bool prime(int);

int main()
{
	int counter = 0;
	
	for (int number = 1; number <= 100000; number++)
	{
	if (prime(number) == 1)
	{
		cout << "Il numero " << number << " e' un numero primo" << endl;
		counter++;
	}
	}

	cout << counter;

	return 0;
}

bool prime(int number)
{
	int a = 0;
	double number2 = number;
	int b = (int)sqrt(number2);
	
	if (number == 1)
		return number != number;
	else
		if (number == 2)
			return number == number;
		else
	if (number % 2 == 0)
		return number != number;
	else
		if (b == number * number)
		return number != number; 
	else
	{
		for (int counter = number - 1; counter > 1; counter--)
		{
			if (number % counter == 0)
				a = 1;
		}
		
	if (a == 1)
		return number != number;
	else
		return number == number;
	}
}

Grazie a tutti per l'aiuto,

Unslee

[unslee]

Problema risolto ....

un riavvio del pc e il mistero del numero 1 si è risolto!

Unslee

[Ziosilvio]

Il numero 1 non è considerato un numero primo.

In caso contrario, l'enunciato del teorema fondamentale dell'aritmetica "ogni intero positivo si riscrive in un modo e uno solo come prodotto di potenze di primi" non sarebbe vero (perché si può moltiplicare per 1 tutte le volte che si vuole) e bisognerebbe usarne uno più complicato.

EDIT: oltretutto, il numero 1 si può comunque ottenere come prodotto vuoto di potenze di primi.

[unslee]

Non si finisce mai di imparare... grazie per la spiegazione. Ho risistemato il programma perché era stato tarato sulla mia ignoranza in materia! Ora gira correttamente.

:

[unslee]

Trovandoci a parlare dei numeri primi, avrei bisogno di aiuto per capire il testo dell'esercizio (del libro dei fratelli Deitel che sto studiando e non di un corso) che recita così:

Un numero intero si dice primo se è divisibile soltanto per se stesso.

a) Scrivere una funzione che determina se il suo parametro è un numero primo

b) Utilizzare questa fuzione per scrivere un programma che determina e visualizza i numeri primi compresi tra 1 e 100.000. Quandi numeri avete bisogno di provare realmente prima di trovare tutti i numeri primi di questo intervallo?

c) Inizialmente penserete che non serve andare oltre n/2 per verificare se n è un numero primo, ma in realtà potete anche fermarvi alla sua radice quadrata. Perché? Riscrivere il programma ed eseguire le due versioni. Che miglioramento avete ottenuto sulle prestazioni?

Mi mette in crisi la c. Ho pensato di filtrare inizialmente i numeri escludendo quelli il cui modulo 2 restituiva 0 (divisibili per due) e mi trovo allineato.
Quando si fa riferimento alla radice quadrata di n l'unica cosa che mi è venuta in mente è che un numero che abbia una radice quadrata intera non sia un numero primo.

Il fatto è che se filtro per la seconda condizione (radice quadrata non intera) che ho pensato il programma degrada in termini di prestazioni rispetto alla prima soluzione (esclusione dei numeri divisibili per due). Nel testo dell'esercizio mi sembra chiaro che le prestazioni debbano aumentare e quindi credo di non aver capito esattamente cosa stia cercando di dirmi il libro nel punto c).

Grazie sempre per l'aiuto,

Unslee

[Ziosilvio]

Originariamente inviato da unslee

Trovandoci a parlare dei numeri primi, avrei bisogno di aiuto per capire il testo dell'esercizio (del libro dei fratelli Deitel che sto studiando e non di un corso) che recita così:

Un numero intero si dice primo se è divisibile soltanto per se stesso.

Questa definizione è talmente sbagliata, che chi ha scritto quel pezzo dovrebbe essere decapitato per manifesta incapacità di usare la testa senza far danni.

Un numero intero maggiore di 1 si dice primo se è divisibile soltanto per 1 e per se stesso.
Equivalentemente: un numero p intero maggiore di 1 si dice primo se le uniche soluzioni intere positive dell'equazione p=x*y sono x=1, y=p ed x=p,y=1.

Originariamente inviato da unslee

Scrivere una funzione che determina se il suo parametro è un numero primo

E fin qui nessun problema.
(A parte il fatto che l'algoritmo ingenuo opera in tempo superpolinomiale nella lunghezza dell'input.)

Originariamente inviato da unslee

Utilizzare questa fuzione per scrivere un programma che determina e visualizza i numeri primi compresi tra 1 e 100.000. Quandi numeri avete bisogno di provare realmente prima di trovare tutti i numeri primi di questo intervallo?

"Quandi numeri avete bisogno"
Ma chi è il redattore, Luca Giurato?

Originariamente inviato da unslee

Inizialmente penserete che non serve andare oltre n/2 per verificare se n è un numero primo, ma in realtà potete anche fermarvi alla sua radice quadrata. Perché? Riscrivere il programma ed eseguire le due versioni. Che miglioramento avete ottenuto sulle prestazioni?

Il "perché" è un teoremino da algebra del primo anno di università.
Pensa a cosa succederebbe se un numero composto avesse solo fattori primi maggiori della propria radice quadrata...

Il libro dovrebbe voler dire che, se fai un confronto tra il tempo che ci mette la versione che prova i divisori fino a n/2 e quella che prova i divisori fino a sqrt(n), noti che la seconda è molto più veloce.
Il problema è che fare delle misurazioni affidabili non è banale, e non so se a questo punto dei tuoi studi conosci già le funzioni di libreria per il computo del tempo...

[shinya]

Ma il punto "b" vorrebbe essere uno spunto per arrivare da soli al crivello di eratostene? Perchè se è cosi mi sembra un pò "vago"...

[unslee]

Ciao Ziosilvio,
peccato per la lontananza altrimenti di chiederei di farmi lezioni di matematica perché sei un asso!

Allora, relativamente alla definizione, quello da decapitare sono io: mi sono sbagliato ed ho mancato un pezzo nella trascrizione!
Anche "quandi" è una mia creazione ...
... chiedo venia e dovrò cercare di essere più attento.

Nel merito del problema sei riuscito a farmi capire (ardua impresa!) esattamente la richiesta del libro. Effettivamente ho fatto girare il programma in entrambi i modi e, anche usando un semplice cronometro (tenendo a bada il più possibile i vari tasks), la differenza di prestazioni è molto visibile.

Questo per me è incomprensibile:
"A parte il fatto che l'algoritmo ingenuo opera in tempo superpolinomiale nella lunghezza dell'input"
Se pensi che per me capire quest'ultima cosa sia utile magari puoi darmi qualche indicazione così mi metto a studiare.

Grazie ancora per l'aiuto,

Unslee

[shinya]

Originariamente inviato da unslee

Questo per me è incomprensibile:
"A parte il fatto che l'algoritmo ingenuo opera in tempo superpolinomiale nella lunghezza dell'input"
Se pensi che per me capire quest'ultima cosa sia utile magari puoi darmi qualche indicazione così mi metto a studiare.

Vuol dire che provare a dividere il numero X per tutti quelli minori della sua radice quadrata non è un metodo molto furbo.
Se li devi testare nel range 1:100000 non so se arrivi in fondo in tempo utile...(no forse fino a 100000 si...ma ad 1 milione credo proprio di no).

[Ziosilvio]

Originariamente inviato da unslee

"A parte il fatto che l'algoritmo ingenuo opera in tempo superpolinomiale nella lunghezza dell'input"
Se pensi che per me capire quest'ultima cosa sia utile magari puoi darmi qualche indicazione

L'algoritmo ingenuo per il test di primalità comporta la divisione del valore n (del quale si vuol sapere se è primo o no) per tutti i numeri primi che non superano la sua radice quadrata.
Il caso peggiore, è che n sia primo oppure il quadrato di un primo, e sia necessario fare tutte le prove.
Se conti il numero T(n) delle operazioni che devi fare nel caso peggiore, e tieni a mente che una stringa binaria che rappresenta il numero n è lunga L=log{2}(n), scopri che per ogni potenza k-esima e per ogni costante C ti ritrovi un valore N(C,k) tale che T(n) >= C*L^k per ogni n > N(C,k)

Si tratta di una branca dell'informatica teorica nota come teoria della complessità.
Puoi vedere qualcosa già su Wikipedia, o sul testo di Cormen, Leiserson e Rivest (se la tua biblioteca ce l'ha).

Originariamente inviato da shinya

Vuol dire che provare a dividere il numero X per tutti quelli minori della sua radice quadrata non è un metodo molto furbo.
Se li devi testare nel range 1:100000 non so se arrivi in fondo in tempo utile...(no forse fino a 100000 si...ma ad 1 milione credo proprio di no).

Purtroppo l'algoritmo di Agrawal-Kayal-Saxena opera sì in tempo polinomiale, ma le costanti moltiplicative nascoste sono talmente grandi, che (salvo grossi progressi in teoria dei numeri) all'atto pratico è più veloce l'algoritmo ingenuo!

[shinya]

Originariamente inviato da Ziosilvio

Purtroppo l'algoritmo di Agrawal-Kayal-Saxena opera sì in tempo polinomiale, ma le costanti moltiplicative nascoste sono talmente grandi, che (salvo grossi progressi in teoria dei numeri) all'atto pratico è più veloce l'algoritmo ingenuo!

Sinceramente, non conoscevo questo algoritmo! Adesso mi documento...
Io mi riferivo al più semplice crivello di eratostene, dato che deve trovare i numeri primi in un range...