Utente:LoStrangolatore/sandboxes/10

Qui di seguito sono presenti alcuni algoritmi per la generazione di numeri primi minori o uguali ad un numero assegnato N. Alcuni di essi si basano sull'osservazione che un numero intero N non può avere divisori maggiori della sua radice quadrata. Per verificare se un numero è primo basta quindi dividerlo per gli interi $2\leq j\leq {\sqrt {N}}$ e calcolare il resto. Se il resto è sempre diverso da zero, allora il numero è primo.

Java

Questo metodo scritto in linguaggio Java consente la stampa in output tutti i numeri primi inferiori al parametro "limitazione".

Si basa su un ciclo che scorre tutti i numeri inferiori al parametro e valuta tramite un secondo metodo di nome "primo" se ogni singolo numero è primo o meno.

    public void stampaNumeriPrimi (int max) {
 
        // Verranno stampati tutti i numeri primi minori di max.
 
        for (int num = 2; num < max; num++)
            if (primo (num))
                System.out.println (num);
    }
 
    /**
     * Restituisce {@code true} se il numero specificato è primo,
     * {@code false} altrimenti.


     */
    protected boolean primo(int numero){
 
        // Istanziamo una variabile di scorrimento
    	// Il numero piu' alto per cui ha senso dividere (se si parte da 2) e'
    	// la radice quadrata del numero che stiamo testando.
        int posMax = (int)Math.ceil(Math.sqrt(numero + 1));

        // Nota: la condizione include un <= e non un <,
        // perché numero potrebbe essere un quadrato perfetto.
        for(int divisore = 2; divisore <= posMax; divisore++)
          if (numero % divisore == 0 && numero!=2) return false; // controlla che il numero sia diverso da 2 unico numero primo pari
        
        // numero non ha divisori.
        return true;
    }

C/C++

Di seguito un algoritmo per la stampa dei numeri primi consecutivi. Si basa sul controllo di ogni singolo numero dispari maggiore di 2 finché non viene raggiunto un limite prestabilito.

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

Pascal

program numeri_primi;
uses crt;
var
	a,b:longint;
	c:real;
begin
clrscr;
	write('Dammi il numero da verificare : '); readln(a);
	b:=a;
	c:=1 + sqrt(a);
	a:=round(c);	
		if a=1 then writeln('1 non è primo')
		else if a=2 then writeln('2 è primo!')
		else if a=0 then writeln('Con tanti numeri che ci sono proprio 0 dovevi scegliere?! -.-')
		else
		begin	
		repeat
			begin
			a:= a -1;			
			end;
		until (a=2) or (b mod a = 0);

		if b mod a = 0 then 
		begin
			a:=b;
			writeln(b,' non è primo!');
			writeln('I suoi divisori sono: ');
				for a:= b-1 downto 2 do
				if b mod a = 0 then write(' ',a,' ');
			writeln(' ');			
		end
		else if a=2 then writeln(b,' è primo!')
		else writeln('ERRORE!');
		end;
end.

Crivello di Eratostene

#include <stdio.h>
#include <stdlib.h>
FILE *pfile;
/*prototipi funzioni*/
void creafile(void);
void crivello_eratostene(long int pvett[], long int *pn);

int main()
{
    long int N, *pvett;

    printf("Software che calcola i numeri primi usando:\nCRIVELLO DI ERATOSTENE\n\n");
    printf("Inserire N:\n");
    scanf("%ld", &N);
    if((pvett= malloc(N*sizeof(long int))) == NULL)
        printf("Insufficient memory!\n\n");
    else
    {
        creafile();
        crivello_eratostene(pvett, &N);
        fclose(pfile);
        printf("esecuzione terminata con successo!\n\nFile creato\n\n");
        free(pvett);  /*distruzione dell'array*/
    }

    exit(EXIT_SUCCESS);
    return 0;
}
/*funzione che crea il file dove salvare i numeri primi*/
void creafile(void)
{
    char nomefile[20];

    printf("Nome da dare al file sul quale salvare i dati:\n");
    scanf("%s", nomefile);
    if((pfile= fopen(nomefile, "w")) == NULL)
    {
        printf("Errore creazione file!\n\n");
        exit(EXIT_FAILURE);
    }

  return;
}
/*funzione che calcola i numeri primi*/
void crivello_eratostene(long int pvett[], long int *pn)
{
    long int i, j;

    for(i=2; i< (*pn); i++) pvett[i]= 1;
        for(j=2; i< i(*pn); i++)
                for(j=2; (i*j)< (*pn); j++) pvett[i*j]= 0;
        /*stampo su file*/
        for(i=2; i< (*pn); i++)
            if(pvett[i])
                fprintf(pfile,"%ld\n", i);
  return;
}

C#

Questo metodo scritto in linguaggio C# consente la stampa in output tutti i numeri primi inferiori al parametro "limite".

Si basa su un ciclo che scorre tutti i numeri inferiori al parametro e valuta tramite un secondo metodo di nome "primo" se ogni singolo numero è primo o meno.

using System;

namespace Numeri_Primi
{
    class Program
    {
        static void Main(string[] args)
        {
            int limite;
            Console.WriteLine("Scrivi Limite:");
            limite = Convert.ToInt32(Console.ReadLine());
            if (limite > 1)
            {
                int pos = 2;
                while (pos <= limite)
                {
                    if (primo(pos)) Console.WriteLine(pos);
                    pos++;
                }
            }
            Console.Read();
        }

        static protected bool primo(int numero)
        {
            int pos = (numero + 1) / 2;
            while (pos > 1)
            {
                if (numero % pos == 0 && pos != numero && pos != 1) return false;
                pos--;
            }
            return true;
        }
    }
}

Python

Questo algoritmo in Python scrive sullo schermo tutti i numeri primi compresi tra due numeri forniti come input.

from math import sqrt

def primo(n):
    if n==0 or n==1:
        return False
    else:
        ris = True
        i = 2
        while i<=sqrt(n):
            if n%i==0:
                i += n
                ris = False
            else:
                i += 1
        return ris

def main():
    a = input(' Da: ')
    b = input('  A: ')
    j = a
    while j<=b:
        if primo(j)==True:
            print j
        j += 1

if __name__=='__main__':
    main()

Per trovare i primi N numeri primi, ci basterà modificare la procedura main nel modo seguente:

def main():
    a = input(' Numeri da trovare: ')
    j = 0
    i = 0
    while j<a:
        if primo(i)==True:
            print i
            j += 1
        i += 1

Visual Basic

Questo algoritmo scrive tutti i numeri primi tra 2 e un numero n.

Private Sub primi2()
        Dim i, b As Integer
        Dim max As Integer = 1000
        Dim numeri(max) As Boolean

        For i = 0 To max
            numeri(i) = True
        Next

        For i = 2 To max / 2
            If numeri(i) = True Then
                For b = i * 2 To max Step +i
                    numeri(b) = False
                Next
            End If
        Next

        For i = 2 To max
            If numeri(i) = True Then
                TextBox1.Text = TextBox1.Text & i & vbCrLf
            End If
        Next
    End Sub

Mantenendo invariato invece il resto del programma.