L'algoritmo che verifichi se un numero è Primo

[Sentenza1]

Ciao a tutti, ho trovato difficoltà nel fare questo algoritmo:

Scrivi un algoritmo che verifichi se un numero è primo.

Lo dovrei fare in pseudolinguaggio, ma non cambia molto, va bene anche in C++. Da quando abbiamo cominciato il ciclo "while" ho cominciato a capirci meno. Non tanto per la funzione del ciclo, o per concetto di "ciclo", ma sono un po perplesso per il contatore, ho capito in parte cosa fa, ma non riesco ancora a risolvere problemi che richiedono questo ciclo. Infatti, questo problema non son riuscito a capire come, più che altro, "scriverlo". Vorrei semplicemente arrivarci insieme a voi, con qualche aiuto, nessuna soluzione. Devo farlo solo con il ciclo while, e non altri. Cercando su internet per aiutarmi ho solo trovato algoritmi con il ciclo for, che non ho ancora studiato.

#include <iostream> 
using namespace std; 


void main() 
{ 
    int div=2; 
    int num; 
    int r; 
     
     
    cout<<"Che Numero Devo Controllare?"<<endl; 
    cin>>num; 

    r=num%div; 

    while (num>div) 
    { 
        if (r==0) 
        { 
            cout<<"il numero non e' primo!"<<endl; 
            div=num+10; 
        } 
        if(r==1) 
        { 
            div=div++; 
        } 
    } 
if (num<div) 
{ 
    cout<<"Fine!"<<endl; 
} 
else
{ 
    cout<<"Il numero e' Primo!"<<endl; 
} 

Ho visto visto questo, ho capito come funziona. L'unica cosa che non mi è chiara, è "div = num+10" e r=num%div;, non ho capito cosa succede in questi punti e cosa significano. Mi aiutereste? Grazie a tutti.

[apatriarca]

Partiamo prima di tutto dall'operatore %. Si tratta di un importante operatore per risolvere il problema che ti è stato dato. Restituisce infatti il resto della divisione tra i due valori. In altre parole restituisce quel valore tale che la seguente proposizione è verificata per ogni intero a e b:

a = (a/b)*b + a%b

Ti ricordo che a/b restituisce la parte intera del quoziente, per cui

1/2 = 0, 1%2 = 1
3/2 = 1, 3%2 = 1
(-7)/5 = -1, (-7)%5 = -2

Quando a%b è uguale a zero, allora b divide a. Vista la definizione di numero primo negli interi, credo che l'importanza di questo operatore è abbastanza evidente.

Non mi è del tutto chiaro come puoi affermare che

Ho visto visto questo, ho capito come funziona.

se non hai compreso quelle due righe di codice. In ogni caso non credo abbia senso. Il procedimento che segue è più o meno il seguente. Legge num e definisce r = num % 2. Entrambi i numeri non cambiano per tutta l'esecuzione del programma. Fa quindi un ciclo che viene eseguito un numero diverso di volte a seconda che il numero sia pari o dispari (e se è pari stampa diverse volte che il numero non è primo). C'è poi una condizione che sarà sempre vera una volta che si è usciti dal ciclo e che quindi stamperà sempre "Fine!". In conclusione non si avvicina neanche un po' al metodo corretto per verificare che num sia o meno primo. Ma dove l'hai trovato questo schifo?

Un metodo semplice utilizzabile in un esercizio di questo tipo è quello di verificare la definizione di numero primo:

Un numero naturale (per comodità voglio considerare solo i numeri positivi) è primo se è maggiore di 1 e se è divisibile solo per 1 e per se stessi.

Il test più semplice (ma anche meno efficiente) consiste nel verificare se esiste un numero compreso tra 1 e se stesso che lo divida. Se questo numero non esiste allora il numero è primo. Ti invito a cercare da solo dei miglioramenti a questo algoritmo. Non è per esempio necessario testare tutti i numeri da $1$ a $n-1$, dopo $n/2$ non esistono ad esempio di sicuro numeri che lo dividano, ma si può fare di meglio.

[Sentenza1]

Ho provato a realizzarne uno io da 0, che stampa N numeri primi. Solo che mi da il flag sempre ad 1, trovate qualche errore? (Grazie apatriarca per la dritta) ;

#include <cstdlib>
#include <iostream>
using namespace std;

int n,c,r,flag;

int main()
{
    cout<<"inserisci il numero da cui determinare i numeri primi"<<endl;
cin>>n;
c=1;
     while (c<n)
         { r=n%c;
              if (r==0)
                 {
                       flag=1;
                 }
                   
           if (flag==1)   {        
           cout<<"il numero"<<c<<" e' primo"<<endl;
                           }
  c=c+1; } 
                          
       
    system("PAUSE");
    return EXIT_SUCCESS;
}

[apatriarca]

No, il codice non è corretto. Vediamo un po' di correggerlo.

int n,c,r,flag;

Le variabili da usare è meglio dichiararle subito prima di utilizzarle in modo da ridurre gli errori e limitarne l'accesso. Dichiararle a scope globale è particolarmente dannoso e adatto solo a programmi giocattolo. Anche se corretto ti consiglio di iniziare fin da subito ad evitare questa pratica. In seguito cercherò di postare il codice corretto per cui sarà forse più chiaro questo consiglio.

c=1; 
     while (c<n) 
         { r=n%c; 
              if (r==0) 
                 { 
                       flag=1; 
                 } 
                    
           if (flag==1)   {        
           cout<<"il numero"<<c<<" e' primo"<<endl; 
                           } 
  c=c+1; }

Formatta il codice decentemente. Un codice ben formattato è più leggibile. In ogni caso il ciclo è completamente sbagliato. Per ogni c che va da 1 a n-1, calcoli il resto di n/c e se questo resto è uguale a zero setti il flag a 1. Se questo flag è uguale a 1 stampi a questo punto che il numero è primo. Ci sono due grossi errori in questo ragionamento e uno più piccolo:
1. (piccolo) qualsiasi numero è divisibile per 1, c dovrebbe quindi iniziare da 2.
2. (grosso) se flag è uguale a 1, cioè è divisibile per qualche c, allora NON è primo.
3. (grosso) la verifica che il numero sia primo va fatta solo dopo aver testato che tutti i numeri non sono divisibili e quindi fuori dal ciclo.

Vediamo quindi il metodo corretto:

#include <iostream>

/*
 * Non ho messo "using namespace std;" per mostrarti in che modo scrivere il programma in sua mancanza.
 * Può essere utile e in effetti alcuni consigliano di farlo.
 */

int main() 
{
    // con il metodo usato, n deve essere positivo per cui forzo questa restrizione usando un tipo senza segno.
    unsigned n; 

    std::cout << "Inserisci il numero da cui determinare i numeri primi.\n"; // \n serve per andare a capo.
    std::cin >> n; 

    unsigned c = 2; // c deve partire da 2 per il discorso fatto prima 
    bool primo = true; // il C++ supporta i tipi booleani che possono assumere come valori solo true e false

    while (c < n) {
        unsigned r = n % c;

        if (r == 0) {
            primo = false; 
        }

        ++c; // un metodo più sintetico per scrivere c = c + 1.
    }

    if (primo) {
        std::cout << "Il numero " << n << " e' primo.\n";
    } else {
        std::cout << "Il numero " << n << " non e' primo.\n";
    }

    // system("PAUSE"); è un obbrobrio e comunque non serve se si usano strumenti decenti
    return 0; // EXIT_SUCCESS è semplicemente 0 e in realtà non ci sarebbe neanche bisogno di inserire questo return perché incluso in automatico.
}

[Sentenza1]

Ti ringrazio tantissimo. Hai usato un sacco di funzioni che a scuola non hanno nemmeno accennato, come per esempio il tipo booleano.