[C] Problemi sui numeri primi

[Manugal]

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]

Originariamente inviato da Manugal

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?

[Manugal]

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.

[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;
}

Con pochissime modifiche svolge entrambi gli esercizi che hai richiesto.

[Fenomeno85]

non mi ricordo bene ma se non ricordo male un mio compagno aveva trovato che bastava andare fino a log del numero o forse era la metà

~§~ Sempre E Solo Lei ~§~

[Ziosilvio]

Originariamente inviato da Manugal

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]

Originariamente inviato da Fenomeno85

non mi ricordo bene ma se non ricordo male un mio compagno aveva trovato che bastava andare fino a log del numero o forse era la metà

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

[Manugal]

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?

[VICIUS]

Originariamente inviato da Ziosilvio

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

[n0ps]

Originariamente inviato da Manugal

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

[cionci]

Originariamente inviato da Manugal

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]

Originariamente inviato da cionci

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

[cionci]

Giusto...basta fare qualche operazione sul contatore...

[Maephisto]

già magari riesci anche a trovare i fattori di un numero in tempo costante o al più polinomiale (chi ha orecchie per intendere... )


ah chiaramente invece per trovare se un numero è primo o meno... quello è facile... da qualche anno

[Manugal]

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

Originariamente inviato da Manugal

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

[Manugal]

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?

[Manugal]

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

[Molz]

La if significa proprio il contrario di quello che dici tu

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

[Manugal]

Ok grazie. Se non avesse messo il continue che sarebbe successo?