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 e calcolare il resto. Se il resto è sempre diverso da zero, allora il numero è primo.
Java
modificaQuesto 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;
}
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;
}
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.
#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#
modificaQuesto 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
modificaQuesto 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
modificaQuesto 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.