[C++] Programma Che Riconosca Se Un Numero E' Primo

[Loris14]

Ciao ragazzi, ho bisogno di creare un programma che dato un numero, riconosca se questo è primo...

Il programma deve essere di questo tipo...

#include <cstdlib>
#include <iostream>
#include <conio.h>
using namespace std;

int main(int argc, char *argv[])
{
    int NUM, ;
    cout << "Dato Un Numero, Dire Se E' Un Numero Primo";
    cout << "\n \n";
    cout << "Inserisci Il Numero: ";   
    cin >> NUM;
    cout << "\n";
    while (  )
       { 
        
       }
    cout << "Testo Finale";
    cout << "\n \n";
    cout << "FINE";
    getch ();
    return EXIT_SUCCESS;
}

Sapete come fare???

Grazie!!!

[clockover]

un numero quando è primo è divisibile solo per lui stesso e uno.. quindi basta che implementi un controllo dei resti della divisione da 1 (escluso) a n-1 (incluso)

[manuel17787]

Devi fare un ciclo da 2 a NUM-1. Ad ogni passo controlli se il resto della divisione tra NUM e il contatore è 0. Se trovi almeno un resto a 0, vuol dire che non è primo, altrimenti è primo..

[Mulder90]

siccome per numeri grandi potrebbe essere necessario molto tempo per vedere se un certo n è primo cerca di semplificarti la vita.
1) se il numero è pari non è primo. quindi if n%2==0 return false
2) il ciclo a questo punto può essere fatto solo sui numeri dispari.
3) con un po di matematica si riesce a dimostrare che non è necessario fare un ciclo che arrivi fino ad n. Infatti basta arrivare fino alla radice di n.

Cerca di fare qualcosa del genere!

[mariusTrio]

Dovresti:
-controllare che sia disparo
-controllare che non abbia fattori

per trovarti i fattori basta fare un ciclo con indice da 3 a N-1, che avanza di 2 ad ogni iterazione (così hai indici solo dispari) poi all'interno del ciclo basta che controlli che il risultato dell'operazione N mod i (dove N è il tuo numero mentre i è l'indice) sia diverso da zero. Se per tutti gli indici il risultato è diverso da zero, allora il numero è un numero disparo.
Buon Lavoro

[cdere]

Originariamente inviato da Mulder90

siccome per numeri grandi potrebbe essere necessario molto tempo per vedere se un certo n è primo cerca di semplificarti la vita.
1) se il numero è pari non è primo. quindi if n%2==0 return false
2) il ciclo a questo punto può essere fatto solo sui numeri dispari.
3) con un po di matematica si riesce a dimostrare che non è necessario fare un ciclo che arrivi fino ad n. Infatti basta arrivare fino alla radice di n.

Cerca di fare qualcosa del genere!

ottimo, quoto Mulder

[Loris14]

Non riesco a scrivere sul programma le cose che mi avete suggerito :S

Sono agli inizi...

[dierre]

Intanto posta quello che hai già scritto.

[tuccio`]

Originariamente inviato da Mulder90

siccome per numeri grandi potrebbe essere necessario molto tempo per vedere se un certo n è primo cerca di semplificarti la vita.
1) se il numero è pari non è primo. quindi if n%2==0 return false
2) il ciclo a questo punto può essere fatto solo sui numeri dispari.
3) con un po di matematica si riesce a dimostrare che non è necessario fare un ciclo che arrivi fino ad n. Infatti basta arrivare fino alla radice di n.

Cerca di fare qualcosa del genere!

be' volendo i numeri primi maggiori di 3, li puoi scrivere tutti nella forma 6k+/-1, quindi volendo non serve neanche guardarli tutti i dispari

[rеpne scasb]

■

[clockover]

Originariamente inviato da rеpne scasb

Se non hai problemi con i numeri molto grandi, e il numero da testare e' piccolo, allora puoi fare in questo modo:

sia 'n' il numero di cui vuoi testare la primalita', calcola la quantita' Q = ((n - 1)! + 1) / n, se intera allora 'n' e' primo altrimenti no.

Io direi di non confondergli troppo le idee.. secondo me meglio che cominci con qualcosa di magari poco efficiente ma semplice da scrivere. Poi ovviamente può renderlo migliore con il tempo.

[hw85]

Ragazzi ho un problema "simile" se qualcuno mi può dare una mano ve ne sarei grato!

http://www.hwupgrade.it/forum/showthread.php?t=2317648

Grazie anticipate!!