[C] Problemi sui numeri primi

[cionci]

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

[Molz]

Originariamente inviato da cionci

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

[cionci]

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

[Manugal]

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

[cionci]

Originariamente inviato da Manugal

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

[Manugal]

Ok grazie vedrò di rifletterci su!

E per quanto riguarda la mia funzione che ho postato, potrebbe essere un'altra soluzione?

[cionci]

Perchè metti un while ? Basta un if... Anzi in questo modo ti si pianta perchè con continue torna al while....

[Manugal]

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 ( ) ; i++). Ho sbagliato qualcosa?

[cionci]

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

[Manugal]

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?

[cionci]

Chiaro che in termini di prestazioni è più veloce, ma anche in termini di qualità... Diciamo che fa più effetto

[cionci]

Originariamente inviato da Manugal

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]

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

[antonio.salini@micso.net]

Potresti cercare di spiegarmi la sintassi della riga for

for(i=2;i*i<=num;i+=num%i?(i&1)+1:2-i)


Grazie

Originariamente inviato da repne scasb

#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);
}

[Kenger]

Originariamente inviato da antonio.salini@micso.net

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

[antonio.salini@micso.net]

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

Originariamente inviato da Kenger

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