[VB] algoritmo

[davide91]

in un problema devo dire se un numero è primo.
il mio problema è quello che non so quale deve essere il blocco di controllo per indicare se un numero è primo.
avete capito?

[Alex_87_xelA]

Quando un numero si dice primo ?

Quando è divisibile per se stesso e per 1.

Quindi se devi vedere se 5 è primo (e lo è :D) devi vedere se è divisibile per 4 (no) 3 (no) 2 (no) 1(si)

4 non è primo perchè : divisibile pr 3(no) 2(si) !!! allora non è primo

ragiona su questo !!!

[Mattyfog]

io l'ho fatto l'anno scorso un programmino del genere.. Devi prendere il numero e provarlo a dividere per tutti i numeri e vedere se la divisione è possibile o da un resto. Se è possibile allora il numero è primo se da un resto aloora vai avanti fino a quando non arrivi ad uno. A quel punto puoi dire che il numero è primo.

[Alex_87_xelA]

io l'ho fatto l'anno scorso un programmino del genere.. Devi prendere il numero e provarlo a dividere per tutti i numeri e vedere se la divisione è possibile o da un resto. Se è possibile allora il numero è primo se da un resto aloora vai avanti fino a quando non arrivi ad uno. A quel punto puoi dire che il numero è primo.

per i numeri precedenti !!!
per il resto è tutto esatto :D

[DanieleC88]

Numeri grandi probabilmente saranno multipli di numeri più piccoli, quindi io direi di far iniziare il controllo dal due (tutti i numeri interi positivi sono divisibili per uno, quindi non ha senso fare quel controllo) e fermarsi ad n/2, dove n è il numero di cui si vuole verificare la primalità (esercizio: perché proprio ad n/2? :D).

Altrimenti un metodo molto simpatico è prepararsi un vettore con una certa quantità di numeri interi, eliminare i numeri non primi (Google: "Crivello di Eratostene"), e poi confrontare quell'array per verificare la primalità (una volta riempito l'array, la consultazione dello stesso richiederà un tempo costante, dando una risposta immediata e senza branch di alcun tipo).

Ci saranno probabilmente anche altri metodi più efficienti ed intelligenti, ma a quest'ora non mi viene proprio nient'altro per la testa. :D

ciao ;)

[Alex_87_xelA]

Numeri grandi probabilmente saranno multipli di numeri più piccoli, quindi io direi di far iniziare il controllo dal due (tutti i numeri interi positivi sono divisibili per uno, quindi non ha senso fare quel controllo) e fermarsi ad n/2, dove n è il numero di cui si vuole verificare la primalità (esercizio: perché proprio ad n/2? :D).

Altrimenti un metodo molto simpatico è prepararsi un vettore con una certa quantità di numeri interi, eliminare i numeri non primi (Google: "Crivello di Eratostene"), e poi confrontare quell'array per verificare la primalità (una volta riempito l'array, la consultazione dello stesso richiederà un tempo costante, dando una risposta immediata e senza branch di alcun tipo).

Ci saranno probabilmente anche altri metodi più efficienti ed intelligente, ma a quest'ora non mi viene proprio nient'altro per la testa. :D

ciao ;)

era ovvio chè l'uno non si debba prendere in considerazione ... TUTTI sono divisibili per esso :D ... io ho solo dato l'idea ... poi il resto toccava a lui ... se poi non riesce sarò pronto a dargli una mano :D

[DanieleC88]

era ovvio chè l'uno non si debba prendere in considerazione ... TUTTI sono divisibili per esso :D ... io ho solo dato l'idea ... poi il resto toccava a lui ... se poi non riesce sarò pronto a dargli una mano :D
Aspe', mi sono spiegato male, io leggendo il tuo codice ho intuito che proponessi una soluzione che cercasse di dividere il numero andando dal numero stesso a numeri più piccoli, io ho semplicemente detto che forse è conveniente partire dal basso, si ha più probabilità di fermarsi dopo un minor numero di passi (e terminando comunque la ricerca ad n/2, dopo non ha più senso proseguire). Cerco solo di minimizzare gli sprechi ed ottimizzarne il tempo finale. :D

ciao ;)

[MarcoGG]

in un problema devo dire se un numero è primo.
il mio problema è quello che non so quale deve essere il blocco di controllo per indicare se un numero è primo.
avete capito?


Non so se è il tipo di risposta che cerchi, ma se quel (VB) sta per Visual Basic :

Public Function testSePrimo(num As Long) As Boolean

Dim div As Long
div = 1
Do While div <= (num / 2)
div = div + 1
If num Mod div = 0 Then
testSePrimo = False
Exit Function
End If
Loop
testSePrimo = True

End Function

e buonanotte al secchio. :D

[Ken1986]

Prova ad implementare il test di Fermat

[cionci]

Numeri grandi probabilmente saranno multipli di numeri più piccoli, quindi io direi di far iniziare il controllo dal due (tutti i numeri interi positivi sono divisibili per uno, quindi non ha senso fare quel controllo) e fermarsi ad n/2, dove n è il numero di cui si vuole verificare la primalità (esercizio: perché proprio ad n/2? :D).)
Direi anche a radice quadrata di n (ovviamente arrotondato per difetto) ;)

[Alex_87_xelA]

Direi anche a radice quadrata di n (ovviamente arrotondato per difetto) ;)

perchè ?

[DanieleC88]

Direi anche a radice quadrata di n (ovviamente arrotondato per difetto) ;)
Vero, hai ragione. ;)

[Alex_87_xelA]

Vero, hai ragione. ;)

perchè ?

[Alex_87_xelA]

da WIKIPEDIA.IT


#include <stdio.h>
#include <stdlib.h>
#include <math.h>

int main();
bool Prime(unsigned int * n);

int main () {
unsigned int l;

printf("\n GENERATORE DI NUMERI PRIMI CONSECUTIVI\n\n");
printf("Inserisci numero limite (maggiore di 1): ");

do {
scanf("%d", &l);
} while (l < 2); // Chiede un numero finché non viene inserito un valore maggiore di 1

printf("\n-\n\nI numeri primi da 0 a %d sono:\n\n2", l);

for(unsigned int a = 3; a <= l; a += 2) { // Genera i numeri da controllare unicamente dispari
if(Prime(&a)) printf("\n%d", a); // Se è primo viene stampato
}

printf("\n\n-\n\n");
system("PAUSE");

return 0;
}

bool Prime(unsigned int * n) {
for(unsigned int b = 2; b <= (unsigned int)(trunc(sqrt(*n))); b++)
if((*n) % b == 0) {
return false;
}
return true;
}

/*Version più veloce :D*/

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

void numeri_primi(int max)
{
int k=max/(int)log(max);
int i,j,pasI=2;int *dp=new int[k];int *m=new int[k];int massimo=1,prova;
dp[0]=5;
m[0]=25;

float temp=clock()/((float)CLOCKS_PER_SEC);
cout<<2<<endl<<3<<endl<<5<<endl;
for(i=7; i<max ;i+=(pasI=6-pasI)) //
{
for(prova=dp[j=0]; (i%m[j])&& prova*prova<i; prova=dp[++j])
{
if(i>m[j]) m[j]+=2*prova;
}
if(i!=m[j])
{
cout<<i<<endl;
dp[massimo]=i;
m[massimo++]=i*i;
}
}
cout<<endl<<"Tempo di esecuzione : "<<clock()/((float)CLOCKS_PER_SEC)-temp<<" secondi";
delete dp;
delete m;
}

main()
{
int i;

cout<<"Introdurre il numero Max : "<<endl;
cin>>i;
numeri_primi(i);
}

[cionci]

perchè ?
N, numero reale, è prodotto di A e B. A e B numeri reali. Per ogni A > sqrt(N), B = N/A, allora B < sqrt(N).
Riportando agli interi la questione non cambia, sia N intero, si ha quindi che sia A divisore intero di N, A > sqrt(N), B = N/A, allora B < sqrt(N).
Se ne deduce che per trovare A e B divisori di N basta cercare B fra i numeri interi <= di sqrt(N) visto che l'altro numero A (A * B = N) è sicuramente >= di sqrt(N).

[Alex_87_xelA]

N, numero reale, è prodotto di A e B. A e B numeri reali. Per ogni A > sqrt(N), B = N/A, allora B < sqrt(N).
Riportando agli interi la questione non cambia, sia N intero, si ha quindi che sia A divisore intero di N, A > sqrt(N), B = N/A, allora B < sqrt(N).
Se ne deduce che per trovare A e B divisori di N basta cercare B fra i numeri interi <= di sqrt(N) visto che l'altro numero A (A * B = N) è sicuramente >= di sqrt(N).

GENIO :D !!! sei un prof o hai rispolverato i libri :D ?
TUTTA QUESTA MATEMATICA :confused: TUTTI QUESTI CONFRONTI :confused:però ho capito :D

gRAZIE mILLE

[cionci]

GENIO :D !!! sei un prof o hai rispolverato i libri :D ?
Solo un pizzico di logica ;) Poi è una cosa di cui si era già parlato qui.