[ALGORITMI] Numeri primi

[Lardoman 2.0]

Qualcuno conosce un algoritmo (indipendentemente dal linguaggio) che permette di determinare se un numero è primo o no ?

Tempo fa avevo sentito dire che non ne esistevano,ma onestamente la cosa mi pare strana :master:

Illuminatemi

[Shagrat]

Il primo che mi viene in mente è dividere il numero specificato per tutti i numeri minori della sua metà, appena trovi una divisione che non dà resto sai che il numero non è primo, altrimenti lo è...

Edit: anzi per ottimizzarepotresti far dividere per tutti i numeri dispari minori della sua metà (aggiungendo a questi il 2)

[Lardoman 2.0]

Originariamente inviato da Shagrat
Il primo che mi viene in mente è dividere il numero specificato per tutti i numeri minori della sua metà, appena trovi una divisione che non dà resto sai che il numero non è primo, altrimenti lo è...

Questo non è un algoritmo...è forza bruta... finche i numeri sono bassi (diciamo sotto le centinaia di miliardi) la cosa è fattibile

Però se io volessi sapere se il numero 10^48 (10 alla 48esima) è primo o no un computer ci metterebbe anni e anni a provare tutte le possibili combinazioni..

A me interesserebbe sapere se c'è un modo universale che sia applicabile a qualunque numero , anche enorme ....

[oregon]

Stai cercando di conoscere uno dei misteri della matematica ...

Se non mi sbaglio per dimostrare la "congettura di Riemann" c'è un premio da 1 milione di dollari ...

Se lo sapessi, prima di dirlo a te, mi prenderei il milione ...

[Lardoman 2.0]

Originariamente inviato da oregon
Se non mi sbaglio per dimostrare la "congettura di Riemann" c'è un premio da 1 milione di dollari ...

Mi potresti spiegare terra-terra in cosa consiste ? Ho provato a cercare su google ma tutti gli articoli che trovo sono estremamente tecnici e le mie conoscenze matematiche alquanto lacunose

[Shagrat]

so cosa vuol dire 10^48, comunque algoritmo (da vocabolario) è un procedimento che ti porta ad un risultato in un numero finito di passi, quindi quello che ti ho detto E' un algoritmo...il fatto che ci metta decine di anni o qualche millisecondo non conta...

cmunque non c'è un metodo meno dispendioso (dimostrato) in termini di tempo...i'm sorry

[Andrea1979]

bhè, intanto, non serve affatto fino alla metà, ma basta fino alla radice quadrata (perchè?).

Un metodo storico è il crivello di Eratostene, ma non fa di certo al caso tuo.

Puoi leggere un po' di roba qui:

http://mathworld.wolfram.com/PrimeNumber.html

Oppure cercare "Mersenne" in google, dovrebbe uscirti, tra i primi risultati, il più grande progetto di ricerca di grandi primi.
Divertiti.

[Lardoman 2.0]

Originariamente inviato da Andrea1979
bhè, intanto, non serve affatto fino alla metà, ma basta fino alla radice quadrata (perchè?).

Un metodo storico è il crivello di Eratostene, ma non fa di certo al caso tuo.

Puoi leggere un po' di roba qui:

http://mathworld.wolfram.com/PrimeNumber.html

Oppure cercare "Mersenne" in google, dovrebbe uscirti, tra i primi risultati, il più grande progetto di ricerca di grandi primi.
Divertiti.

Grazie

C'è da perderci la testa

[fillo_84]

E' una delle pietre miliari della matematica, trovare un algoritmo in grado di determinare numeri primi di qualsiasi entità, così facendo si eviterebbero milioni di calcoli per trovarne di nuovi, e quindi milioni di calcoli x effetuare l'operazione contraria.

Sembra che Riemann avesse in realtà la soluzione, ma non è mei stata trovata, xkè lui non scriveva le sue dimostrazioni x paura che gliele rubassero.

Cmq penso che se trovi la soluzione, oltre prenderti un milione di dollari, e un nobel, potresti ritrovarti nel gotha degli scienziati, almeno al pari di gauss.....


X questo non esiste un metdo poco dispendioso.....

[oregon]

Originariamente inviato da fillo_84
Sembra che Riemann avesse in realtà la soluzione, ma non è mei stata trovata, xkè lui non scriveva le sue dimostrazioni x paura che gliele rubassero.

Altre fonti dicono che la dimostrazione l'avesse scritta ma che una sua domestica molto zelante, nel mettere a posto la stanza, avesse gettato tutti "quei fogli sparsi con strani segni" ... VVoVe:

Originariamente inviato da fillo_84
Cmq penso che se trovi la soluzione, oltre prenderti un milione di dollari, e un nobel, potresti ritrovarti nel gotha degli scienziati, almeno al pari di gauss.....

Ma il nobel non lo prenderebbe perche' non esiste per la matematica ... semmai la medaglia Fields ...

Originariamente inviato da Lardoman 2.0
Mi potresti spiegare terra-terra in cosa consiste ? Ho provato a cercare su google ma tutti gli articoli che trovo sono estremamente tecnici e le mie conoscenze matematiche alquanto lacunose

No ... non te lo potrei spiegare terra terra ...

Se vuoi approfondire, ti consiglio di studiare "la funzione Z di Riemann" e "i suoi zeri" ...