[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 è ) 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]

Originariamente inviato da 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.

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

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

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.

ciao

[Alex_87_xelA]

Originariamente inviato da 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? ).

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.

ciao

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

[DanieleC88]

Originariamente inviato da Alex_87_xelA

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

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.

ciao

[MarcoGG]

Originariamente inviato da 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?

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.

[Ken1986]

Prova ad implementare il test di Fermat

[cionci]

Originariamente inviato da 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? ).)

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

[Alex_87_xelA]

Originariamente inviato da cionci

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

perchè ?

[DanieleC88]

Originariamente inviato da cionci

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

Vero, hai ragione.

[Alex_87_xelA]

Originariamente inviato da DanieleC88

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]

Originariamente inviato da Alex_87_xelA

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]

Originariamente inviato da cionci

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 !!! sei un prof o hai rispolverato i libri ?
TUTTA QUESTA MATEMATICA TUTTI QUESTI CONFRONTI però ho capito

gRAZIE mILLE

[cionci]

Originariamente inviato da Alex_87_xelA

GENIO !!! sei un prof o hai rispolverato i libri ?

Solo un pizzico di logica Poi è una cosa di cui si era già parlato qui.