numeri primi

[bDaniele]

chi può indicarmi un algoritmo per stabilire se un numero è primo o no?

non mi serve codificato in qualche linguaggio particolare, mi basta l'algoritmo poi lo traduco io.

grazie.

[floyd]

il primo che mi viene

int x = 20;
if (x%2 == 0)
return;
for (int i=3; i<x; i+=2)
if (x%i == 0)
return;

un altro molto più veloce sarebbe fare un array di numeri da 2 al numero che vuoi calcolare, togliere tutti i multipli (6,9,12 via) e dividere il numero per gli elementi rimasti

[chipdb]

preso in input il numero n:

if n<=3
primo=true
else
if n mod 2=0 then

[chipdb]

Sorry x il messaggio sopra incompleto.

Preso in input il numero n:

if n<=3
primo=true
else
if n mod 2=0 then
primo=false
else
d=3
r=int(sqrt(n))
while (num mod d<>0) and (r<d)
d=d+2
end while
if r>d then
primo=true
else
primo=false
end if
end if
end if

Così dovrebbe andare. Non ho controllato, sono andato a memoria. Bye

[bDaniele]

non funziona!!!!

dimmi il significato delle variabili "r" e "d"
nel while (num mod d<>0) and (r<d) num dovrebbe essere "n"??

grazie

[chipdb]

Ho controllato, ecco il codice giusto

If n <= 3 Then
primo = True
Else
If n Mod 2 = 0 Then
primo = False
Else
d = 3
r = Int(Sqr(n))
While (n Mod d <> 0) And (r < d)
d = d + 2
Wend
If r > d Then
primo = False
Else
primo = True
End If
End If
End If

L'algoritmo controlla inizialmente se il numero é minore o uguale a 3, e cioé é primo. Se invece é divisibile per 2 allora non é primo. Quindi partendo da 3 (d=3) e arrivando fino all'intero della radice del numero ( r=Int(Sqr(n)) ) ad intervalli di 2 (3-5-7-9 ecc.) se il programma trova un divisore (n Mod d <> 0) allora il numero non é primo (r > d), altrimenti si.

Spero di essermi spiegato.

Bye

[vonkranz]

....opssss....

[Popper]

secondo me basta una singola if....

static boolean isPrimo(int numero){
boolean result = true;
int i;
for (i = numero - 1; i > 1 && result ; i--)
result = ((numero % i ) != 0);
return result;
}7

[chipdb]

Hai provato a controllare la computazionalità tra i due algoritmi?
Perché dover arrivare fino al numero se il numero é solo 2 o 3 che sono primi ?
Perché dover arrivare fino al numero se é pari (il che implica che non é primo) :tongue:?

Ciao

[hmesfet]

Ho giusto un programmino in C della prima settimana
di corso del primo anno di ingegneria hi..hi(Poli di torino)
L'algoritmo riguarda la definizione di numaro primo:
"Un numero intero si dice primo se e solo se è divisibile
per 1 e per se stesso"
Quindi i numeri pari sono evidentemente non primi(tutti divisibili per 2).La ricerca viene fatta solo sui numeri dispari,quindi si
controlla che il numero inserito non abbia divisori a partire
da 2 fino a numero/2(gli altri numero/2 +1,.. danno tutti
resto diverso da zero quindi è inutile tenerne conto),
tenendo presente che dati a e b entrambi interi a è divisibile
perb se e solo se
il resto della divisione a/b è zero.
ESEMPIO
a=17; allora divido a per 2,3,...,a/2 nota:a/2=17/2=8
(divisione fra interi !)
e controllo che il resto delle divisioni sia
diverso da zero,se tutti i resti sono diversi da zero
allora a è divisibile soltanto per 1 e per se stesso
ovvero come da definizione "a è 1 numero primo"
17/2=8 resto 1
17/3=5 resto 2
17/4=4 resto 1
17/5=3 resto 2
17/6=2 resto 5
17/2=7 resto 3
17/8=2 resto 1
tutti i resti sono diversi da zero=>17 è 1 numero primo
NOTA:17/9=1 resto 8,....,17/16=1 resto 1 è sempre cosi'
per quello non ne teniamo conto e usiamo solo
i divisori fino ad a/2=17/2=8
POTENZA DEL POLI DI TORINO!!!!!!!!!!

#include <stdlib.h>
#include <stdio.h>
#include <limits.h>
#define NUM "c:\\numeri.txt"
#define MOD_R "r"
#define MOD_W "w"
#define MSG "non riesco ad aprire il file\n"
/*
Name: numeri_primi
Author:zax
Description:ho usato 1 file per memorizzare i divisori
poiche il loro numero nn è noto a priori
Date:
Copyright:
*/
typedef enum{fal,tru}boolean;
typedef FILE* file;
typedef char* string;/*ho definito il tipo stringa*/
void open_(string);
file fp;
int main(void)
{
boolean state=fal;
int i=0;
int state1,div,j;
unsigned int num;
char s1[80];
printf("Calcolo dei numeri primi\n");
printf("1 unsigned occupa %d byte,valore max %u\n",sizeof(unsigned int),UINT_MAX);
do
{

if(i&&(state))
{
printf("numero:");
state1=scanf("%*c%u",&num);/*il carattere viene soppresso*/
state=fal;
}
if((!state)&&(!i))
{
printf("Inserire un numero dispari:");
state1=scanf("%u",&num);
printf("\n");
}
if((num%2!=0)&&(num>0)&&(state1))
;/*ha letto correttamente*/
else
state=tru;

i++;
}while(state);/*esce con state==fal*/
div=num/2;

for(i=3,j=0;i<div;i++)
{
if(!(num%i))
{
printf("%d\n",i);
if(!j)
{
open_(MOD_W);
j++;
fprintf(fp,"NUMERO %u divisori\n",num);
}
fprintf(fp,"%d\n",i);/*scrivo su file i divisori*/
state=tru; /*ha divisori*/
}
}
if(state)
{
fclose(fp);
open_(MOD_R);
}

printf((state)?"%u numero non primo,seguono i divisori:\n":"%u numero primo\n",num);
i=0;
if(state)
{
fgets(s1,80,fp);
while(fscanf(fp,"%u",&num)!=EOF)
{
i++;
printf("%d)divisore=%u\n",i,num);
}

fclose(fp);
}
printf("%s\n",s1);

system("PAUSE");
return 0;
}

void open_(string s)
{
if((fp=fopen(NUM,s))==NULL)
{
printf(MSG);
system("pause");
exit(1);
}
}

Fai copia e incolla..