[C/C++]: Determinare se un numero è primo

[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

[alka]

Il linguaggio? Hai letto il Regolamento? :master:

[VanessaInfo]

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

VVoVe: 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]

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]

...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]

grazie lo provo subito

max

[maxx1]

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]

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))

[maxx1]

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