programma in C che, dato un numero, riconosce se è un numero primo?

[mark_1]

salve tutti!
all'università sto frequentando un corso di programmazione in C...
e un esercizio per allenarsi è di creare un programma che, dato un numero dall'utente, riesca a riconoscere se è un numero primo e stampi la frase "è un numero primo" (ma va?!?!?)
il problema è che è da un'ora che ci provo e non ho risultati, non funzionanti almeno.
quindi BARO:evil: e chiedo aiuto a voi!

heheheh

per ora ho fatto:

• if-else
• connettori logici (&&,||,!)
• for
• while
• do while
• array
• tipi int e char

grazie della cortese attenzione:inchino:

 

[beppenike]

edit: ho trovato questo
Il più antico e semplice test di primalità è quello di "divisione per tentativi", che consiste nell'applicare direttamente la definizione di numero primo: si prova a dividere il numero N per tutti i numeri minori di N: se nessuno di questi lo divide, allora il numero è primo. Un semplice miglioramento di questo metodo si ottiene limitando i tentativi di divisione ai numeri primi minori radice quadrata di n.

 

[mark_1]

purtroppo i numeri primi non sono calcolabili e si presentano in modo casuale, c'hanno scritto anche un libro su questo ma ancora non hanno risolto la questione.

:look::look::look:

diciamo anche piu' di un libro...
e diciamo che lo sapevo....
:lol::lol::lol:
il mio programma deve dire su un numero che inserisce un utente
sia un numero primo...
per esempio:
non vanno bene tutti i numeri divisibili per 2 tranne 2.
poi trqamite un ciclo while si potrebbe dividere il tale numero inserito dall'utente per tutti i suoi predecessori.
se la divisione darà sempre resto != da 0 (apparte diviso 1 e diviso se stesso)...
il numero sarà necessariamente primo, o almeno credo -spero-.

 

[mark_1]

edit: ho trovato questo
Il più antico e semplice test di primalità è quello di "divisione per tentativi", che consiste nell'applicare direttamente la definizione di numero primo: si prova a dividere il numero N per tutti i numeri minori di N: se nessuno di questi lo divide, allora il numero è primo. Un semplice miglioramento di questo metodo si ottiene limitando i tentativi di divisione ai numeri primi minori radice quadrata di n.

peccato che su C non sia presente la radice quadrata....
o almeno non in "stdio.h" che è quello che usiamo per ora:boh::boh:

 

[giov89]

Per usare la radice quadrata devi importare la libreria "math.h".
Ti consiglio di usare l'operatore modulo per verificare se il numero è primo o meno. Esempio: 5 % 2 restituisce 1. (5 / 2 = 2, resto 1.)

 

[kugfi76r7ifukfg]

isprime(int a)
{
if (!(a % 2)) return 0;
int i;
for (i = 3; i <= sqrt(a); i += 2)
if (!(a % i))
return 0;
return 1;
}

Questa ritorna 1 (vero) se è primo.
Richiede (come detto sopra) la math.h

 

[mark_1]

senza usare math.h?
è impossibile?

comunque grazie!

 

[sebax]

isprime(int a)
{
if (!(a % 2)) return 0;
int i;
for (i = 3; i <= ((a/2)+1); i += 2)
if (!(a % i))
return 0;
return 1;
}

così in teoria, però tieni conto che fai parecchie iterazioni non necessarie (quelle tra radice di a e a/2 +1 )

 

[kugfi76r7ifukfg]

Esatto! :)

Prego comunque.