PDA

Visualizza la versione completa : [C/C++]: Determinare se un numero è primo


maxx1
24-08-2006, 14:07
salve a tutti ,sto cercando di fare una semplice funzione che verifichi se un numero immesso sia primo mi potete dare una mano ?
come suggerimento il testo mi dice di usare semplici divisioni per numeri interi...ma non ci arrivo.. è gradito qualsiasi indizio su come fare ...grazie ancora!

MAX

alka
24-08-2006, 14:14
Il linguaggio? Hai letto il Regolamento (http://forum.html.it/forum/showthread.php?s=&threadid=973887)? :master:

VanessaInfo
24-08-2006, 14:54
Originariamente inviato da maxx1
salve a tutti ,sto cercando di fare una semplice funzione che verifichi se un numero immesso sia primo mi potete dare una mano ?
come suggerimento il testo mi dice di usare semplici divisioni per numeri interi...ma non ci arrivo.. è gradito qualsiasi indizio su come fare ...grazie ancora!

MAX

:oVVoVe: al di là del linguaggi il senso è....

fare un ciclo ke parta da 2 (tanto per uno solo tutti divisibili no?) ed arrivi alla metà del numero (arrodondata per eccesso ad intero) (è suficiente per sapere se è primo o quali divisori ha)...fai il mod (ovvero il resto) della divisione per quel numero e esci quando trovi il primo num divisore.

es.: 10
2 - sì - > ESCE non è PRIMO


es.: 7
2 - no (1°div - potrest uscire quando trova il primo, invece d contarli)
4 - no
PRIMO

VaneX

Spero d aver scritto in modo kiaro e senza cavolate! :-)

maxx1
24-08-2006, 15:22
ringrazio per l'appunto il moderatore, il linguaggio è il C++ ,comunque gradivo anche una risposta in termini di algoritmo ringrazio in tal senso Vanessa...ma se qualcuno ha un idea migliore mi farebbe una cortesia..Max

VanessaInfo
24-08-2006, 15:27
...cosa ha ke nn va la mia? il numero d operazioni sono al minimo 1 (se trova subito divisore) e al max n/2.

VaneX

in effetti...
da un altro forum:

http://www.itsistemi.net/viewtopic-271071.html
E' sufficiente qualche semplice accorgimento per migliorare
notevolmente le prestazioni:


bool calcolo(int n)
{
if (! n%2) return false;

int radice = int( sqrt(n) )

for (int j=3; j<=radice; j+=2)
{
if (!n%j) return false;
}
return true;
}

con queste modifiche vengono considerati soltanto i numeri dispari fino
alla radice di n·
Per es· per testare se 2010545359 e' primo bastano circa 22 mila
confronti invece di 2 miliardi‚ e il tempo di esecuzione passa dal
minuto a qualche millisecondo·
Ovviamente per numeri molto piu' grandi (centinaia di cifre) il
problema resta comunque intrattabile·

Saluti‚

Fabio

maxx1
24-08-2006, 15:39
grazie lo provo subito

max

maxx1
24-08-2006, 19:02
ho provato questa semplice applicazione ...ma non mi funziona..mi ci dai un occhio?
grazie max

#include <iostream.h>
#include <stdlib.h>
int test_primo(int n)
{
int i;
for(i=2;i<n;i++)
{
if (!n%i)
return 1;
}
return 0;
}
int main()
{
int n;
cin>>n;
cout<<test_primo(n);

system("PAUSE");
return 0;
}

U-bahn
24-08-2006, 19:36
if (!n%i)
questo equivale a if ((!n) % i) che, davvero,
non ha senso: !n è sempre 0 se n != 0...e non puoi
dividere 0 per i sperando di ottenere un resto :)

cambialo in if (!(n % i))

:ciauz:

maxx1
24-08-2006, 19:43
sei veramente un grande!!!!

avevo la soluzione sotto gli occhi....e non la vedevo.
( è il caso che ridia un'occhiata alla tabella delle verità e agli operatori)

Grazie ancora

maxx

Loading