View Full Version : [C] Problemi sui numeri primi
Ciao a tutti! :) Spero di non scocciarvi troppo però sto cercando di imparare.
Allora il testo mi dice costruire una funzione int is_prime(int n) che restituisce 1 se il numero n è primo 0 altrimenti. Fino a qui ok. Ma lui mi da un suggerimento dicendomi che se ke n sono interi positivi, k divide n se e solo se n%k vale zero. Quello che non capisco è che se la funzione riceve solamente n come parametro che valore dovrebbe assumere k? E da dove se lo va a pigliare sto k?
Poi di problema ce n'è un altro che dice di scrivere una funzione che trovi tutti i fattori di una dato numero. E qui proprio sono a corto di idee. Come faccio a dirglielo?
Grazie ancora per il vostro prezioso aiuto.
Ziosilvio
25-06-2005, 18:33
il testo mi dice costruire una funzione int is_prime(int n) che restituisce 1 se il numero n è primo 0 altrimenti.
Un esercizio classico.
lui mi da un suggerimento dicendomi che se ke n sono interi positivi, k divide n se e solo se n%k vale zero. Quello che non capisco è che se la funzione riceve solamente n come parametro che valore dovrebbe assumere k? E da dove se lo va a pigliare sto k?
Altro suggerimento: usa i cicli e le variabili locali.
Poi di problema ce n'è un altro che dice di scrivere una funzione che trovi tutti i fattori di una dato numero. E qui proprio sono a corto di idee. Come faccio a dirglielo?
Usi un ciclo su una variabile locale, come nell'esercizio precedente; e quando trovi divisibilità, effettui una stampa.
(Se ho capito bene, è ancora prestino per le liste.)
P.S.: Su che libro stai studiando?
Il testo è: Al Kelley - Ira Pohl - Didattica e Programmazione C - Addison/Wesley Pearson
Cmq non ho ben capito "usa i cicli e le variabili locali". k da dove esce fuori? Se non ha un valore prefissato (o che cmq gli passo io da un'altra funzione) come fa un numero fissato n e essere divisibile per un ipotetico numero k. Lui non sa che valore ha k quindi come fa a stabilire se è primo no? Spero di essermi spiegato.
int main ()
{
int numero;
int div, i;
printf ("Inserisci il numero\n");
scanf ( "%d", &numero );
div = numero;
for ( i = 2; div > 1; ) {
if (! ( div % i ) ) {
printf ( "%d --> %d e' divisibile per %d e resta %d\n",
numero, div, i, div/i );
div /= i;
continue;
}
i ++;
}
return 0;
}
Con pochissime modifiche svolge entrambi gli esercizi che hai richiesto.
Fenomeno85
25-06-2005, 20:12
non mi ricordo bene ma se non ricordo male un mio compagno aveva trovato che bastava andare fino a log del numero :D o forse era la metà :D
~§~ Sempre E Solo Lei ~§~
Ziosilvio
25-06-2005, 20:57
Il testo è: Al Kelley - Ira Pohl - Didattica e Programmazione C - Addison/Wesley Pearson
Mi sembra di ricordare che sia un buon testo.
non ho ben capito "usa i cicli e le variabili locali". k da dove esce fuori? Se non ha un valore prefissato (o che cmq gli passo io da un'altra funzione)
Oppure, che gli assegni tu dall'interno della funzione.
E qui mi fermo, perché adesso è ora che ti impratichisca un po' tu ;)
Ziosilvio
26-06-2005, 10:24
non mi ricordo bene ma se non ricordo male un mio compagno aveva trovato che bastava andare fino a log del numero :D o forse era la metà :D
Era la radice quadrata: se un numero non è primo, allora ha un fattore primo che non supera la sua radice quadrata.
Meglio di così non puoi fare, i controesempi sono i quadrati dei primi.
ESERCIZIO: dimostrare, che è facile ;)
Forse ci sono.
Potrei fare un ciclo for con k che va da 2 a n (n escluso) e vedere se per ogni k n è divisibile per quel k. Se non lo è è primo. E' giusto?
Era la radice quadrata: se un numero non è primo, allora ha un fattore primo che non supera la sua radice quadrata.
Meglio di così non puoi fare, i controesempi sono i quadrati dei primi.
ESERCIZIO: dimostrare, che è facile ;)
Se puo interessare c'è gia la mia dimostrazione nel Thread di qualche tempo fa sul thread del Crivello di Eratostene.
ciao ;)
Forse ci sono.
Potrei fare un ciclo for con k che va da 2 a n (n escluso) e vedere se per ogni k n è divisibile per quel k. Se non lo è è primo. E' giusto?
Si ma guarda che è quello che fa il codice che ti ho postato prima :fagiano:
Forse ci sono.
Potrei fare un ciclo for con k che va da 2 a n (n escluso) e vedere se per ogni k n è divisibile per quel k. Se non lo è è primo. E' giusto?
Vai fino a sqrt(n)...
Ziosilvio
27-06-2005, 10:07
Vai fino a sqrt(n)...
E mi raccomando: non c'è bisogno di includere math.h e chiamare sqrt, si può fare tutto con l'aritmetica intera... ;)
Giusto...basta fare qualche operazione sul contatore...
Maephisto
27-06-2005, 11:10
già magari riesci anche a trovare i fattori di un numero in tempo costante o al più polinomiale :mc: (chi ha orecchie per intendere... :cry: :cry: )
ah chiaramente invece per trovare se un numero è primo o meno... quello è facile... da qualche anno :muro:
int main ()
{
int numero;
int div, i;
printf ("Inserisci il numero\n");
scanf ( "%d", &numero );
div = numero;
for ( i = 2; div > 1; ) {
if (! ( div % i ) ) {
printf ( "%d --> %d e' divisibile per %d e resta %d\n",
numero, div, i, div/i );
div /= i;
continue;
}
i ++;
}
return 0;
}
Io ho fatto così:
for (k=2; k<n; k++)
if(k%n)
return 0;
else
return 1;
Non mi sembra che sia proprio uguale al tuo (anche perché il tuo non l'ho proprio capito :mbe: ). Ma perché complicarsi sempre la vita? (Non è per qualcosa, è che sono agli inizi e non riesco a capire questo codice così "sofisticato"). :) Grazie cmq
FedeX_65246X
27-06-2005, 20:50
Io ho fatto così:
for (k=2; k<n; k++)
if(k%n)
return 0;
else
return 1;
Ti consiglio di ricominciare da zero con il C, prenditi tempo e studia la soluzione proposta più sopra. ;)
Inoltre non pretendere di risolvere un problema senza aver ben chiaro di cosa si tratta, i numeri dispari non sono i numeri primi.
Buon lavoro, ci sono passato anch'io :)
Scusa però ti dico che il mio funziona perché se metto 9 come valore (che è dispari ma non è primo) la funzione mi restituisce correttamente 0. Qundi che ha di sbagliato il mio ciclo?
Cmq sto provando lo stesso a vedere quel codice scritto gentilmente da n0ps:
int main ()
{
int numero;
int div, i;
printf ("Inserisci il numero\n");
scanf ( "%d", &numero );
div = numero;
for ( i = 2; div > 1; ) {
if (! ( div % i ) ) {
printf ( "%d --> %d e' divisibile per %d e resta %d\n",
numero, div, i, div/i );
div /= i;
continue;
}
i ++;
}
return 0;
}
Non capisco bene la if e il div/=i. Cioè la if è come se dicesse if div % i !=0 giusto? Se così fosse come fa il numero a essere divisibile per i (dato che il resto è diverso da 0)? Poi non capisco dopo perché fa div/=i. Grazie a chi mi darà delucidazioni :)
La if significa proprio il contrario di quello che dici tu :D
se il numero è divisibile per i
div % i fa 0
il ! è l'operatore booleano not che applicato a 1 espressione booleana la fa diventare false se è vera e vera se è falsa.
Siccome il valore 0 corrisponde a un espressione booleana falsa allora !0 = vero
quindi if (! ( div % i ) ) è lo stesso che scrivere if ((div % i)==0)
div /=i è lo stesso che scrivere div = div /i
Quel ciclo trova tutti i fattori primi di un numero, se non facesse quella divisione (a parte che il ciclio non terminerebbe mai) risulterebbe che 12 è divisibile per 2, poi per 2, poi per 3, poi per 4, poi per 6 e poi per 12.
Quando l'output giusto è 2 2 3
Ok grazie. Se non avesse messo il continue che sarebbe successo?
Il continue lì non va messo...anzi, ci va messo un break... Infatti se hai trovato un divisore diverso dal numero stesso e da 1 il numero non è primo ;)
Il continue lì non va messo...anzi, ci va messo un break... Infatti se hai trovato un divisore diverso dal numero stesso e da 1 il numero non è primo ;)
Sì be questo è vero se vuoi fare un programma che valuta se un numero è primo oppure no.
Il codice di n0ps però era un po' diverso e mostrava a video tutti i fattori primi di un numero.
In tal caso il continue serve per ridividere il numero da testare ancora per il numero di test.
Ad esempio 12 è divisibile 2 volte x 2, il continue serve appunto a far sì che la divisione venga fatta 2 volte
Comunque diciamo che il programma si può semplificare molto...
Ad esempio è inutile dividere il numero da testare per i multipli di 2 (in teoria sarebbe inutile dividerlo per i multipli di tutti i numeri già testati)...
Ad esempio questo è già più semplice, anche da capire...
int isprime(int n)
{
int i;
int lim = (int)sqrt(n);
if((n % 2) == 0) return 0;
for(i=3; i <= lim; i+=2)
if((n % i) == 0)
return 0;
return 1;
}
E quello che avevo fatto io (parlo sempre della funzione isprime() non di quella per trovare fattori primi quella è un'altra) va bene lo stesso?
int isprime(){
int k;
for (k=2; k<n; k++){
while(n%k!=0){
continue;
}
return 1;
}
return 0;
}
(L'ho un pò modificata perché mi sono accorto che nella versione che ho scritto qui precedente, in pratica faceva il confronto solamente con k=2). Così potrebbe andare? Grazie.
Cmq cionci del tuo programma non ho capito perché consideri la radice quadrata del numero n per vedere se quello è primo o no. Scusa ma in matematica non brillo moltissimo :(
Cmq cionci del tuo programma non ho capito perché consideri la radice quadrata del numero n per vedere se quello è primo o no. Scusa ma in matematica non brillo moltissimo :(
Suppondendo n = q*q, supponendo k > q divisore di n: k*q > n, e quindi con k*j = n, j < q...di conseguenza avresti già evidenziato che il numero non è primo prima di arrivare a q (visto che j < q).
Quindi il numero può avere benissimo divisori maggiori di q, ma la ricerca fino a q proverebbe già che il numero non è primo...
Ok grazie vedrò di rifletterci su! ;)
E per quanto riguarda la mia funzione che ho postato, potrebbe essere un'altra soluzione?
Perchè metti un while ? Basta un if... Anzi in questo modo ti si pianta perchè con continue torna al while....
:doh: che stupido che sono hai ragione!! :) Grazie. Vedrò di riflettere su quel fatto anche se mi è ancora un pò oscuro il fatto della radice quadrata. Io ho provato il tuo codice per esempio con il numero 5. La radice quadrata di 5 è 2,2 che, siccome viene fatto un cast a int, viene arrotondata per difetto (o sbaglio?). Quindi arriviamo al ciclo for (i=3; i<=2 ( :mbe: ) ; i++). Ho sbagliato qualcosa?
Sì, va bene che arrivi a due...
Per farti un esempio:
54 è divisibile per 27, 18, 9, 6, 3, 2...
54 = 27 * 2
54 = 18 * 3
54 = 9 * 6
54 = sqrt(54) * sqrt(54)
La radice quadrata (arrotondata) di 54 è 7... Come vedi arrivando fino a 7 escluderemmo comunque tutte i divisori di 54 (anche se si ferma subito a 2)...
Come vedi se c'è un fattore maggiore di sqrt(54), l'altro è minore di sqrt(54)...quindi testando solo quelli minori o uguali a sqrt(54) escludi automaticamente anche i fattori maggiori di sqrt(54)...
Ok e quindi una volta che considero solo i fattori minori della radice chi mi garantisce la primalità del numero? Se avessi considerato tutti i fattori non lo potrei trovare ugualmente? O forse in termini di prestazioni è conveniente usare questo qui?
Chiaro che in termini di prestazioni è più veloce, ma anche in termini di qualità... Diciamo che fa più effetto ;)
Ok e quindi una volta che considero solo i fattori minori della radice chi mi garantisce la primalità del numero?
Te lo garantisce per il motivo sopra...perchè è inutile controllare quelli maggiori della radice...
repne scasb
29-06-2005, 19:06
Poi di problema ce n'è un altro che dice di scrivere una funzione che trovi tutti i fattori di una dato numero. E qui proprio sono a corto di idee. Come faccio a dirglielo?
#include <stdio.h>
void main(void)
{
unsigned long num,i;
printf("Numero da fattorizzare: ");
scanf("%9ld",&num);
printf("\n%ld=",num);
for(i=2;i*i<=num;i+=num%i?(i&1)+1:2-i)
{
if(num%i==0)
{
printf("%ld*",i);
num/=i;
}
}
printf("%ld\n",num);
}
Potresti cercare di spiegarmi la sintassi della riga for
for(i=2;i*i<=num;i+=num%i?(i&1)+1:2-i)
Grazie
#include <stdio.h>
void main(void)
{
unsigned long num,i;
printf("Numero da fattorizzare: ");
scanf("%9ld",&num);
printf("\n%ld=",num);
for(i=2;i*i<=num;i+=num%i?(i&1)+1:2-i)
{
if(num%i==0)
{
printf("%ld*",i);
num/=i;
}
}
printf("%ld\n",num);
}
Potresti cercare di spiegarmi la sintassi della riga for
for(i=2;i*i<=num;i+=num%i?(i&1)+1:2-i)
Grazie
for(i=2 ; i*i<=num ; i+=num%i ? (i&1)+1 : 2-i)
Il terzo argomento del for (quello dove di solito c'è i++ per intenderci) è un if ternario. Sarebbe stato uguale scrivere
if(num%i)
i+=(i&1)+1
else
i+=2-i
Chiarissimo , ti ringrazio, visto che sei così bravo, avrei bisogno, per uno studio che sto facendo, come si fa a poter rappresentare la scomposizione di un numero in fattori primi con la dicitura es. 16 =2^4 , 6= 2^1*3^1 etc.
Grazie anticipatamente
for(i=2 ; i*i<=num ; i+=num%i ? (i&1)+1 : 2-i)
Il terzo argomento del for (quello dove di solito c'è i++ per intenderci) è un if ternario. Sarebbe stato uguale scrivere
if(num%i)
i+=(i&1)+1
else
i+=2-i
vBulletin® v3.6.4, Copyright ©2000-2025, Jelsoft Enterprises Ltd.