Algo de recherche de nombres premiers - Page 1

Bon puisque je fais un TIPE sur la recherche des nombres premiers, je me doit de chercher l'algo le plus pratique.
En pratique sur pc, on utilise il me semble le crible.
Or, si je veux appliquer ceci sur ti, je serai vite depassé en memoire!
C'est donc la raison pour laquelle j'ai commencer a chercher une formule, et j'ai trouver:

ISPRIME(k)=k-sum(E(k/p),pE|P(k))
ISPRIME = 1 si le nombre est premier, 0 sinon.

explication sur la formule:
E(k/p) est la parite entiere de k/p, ce qui est tres pratique pour les calcules sur pc (pas de float)
pE|P(k), est p, appartenant a l'ensemble |P(k) etant l'ensemble des nombres premiers inferieurs a k.

L'avantage, est que l'on ne stoque en memoire que les nombres premiers qui demande moins de plance que tous les nombres naturels. (il suffit de regarder l'etude de pi(x)...)

Je lance le defi...

Je comprends que tu veuilles eviter l'utilisation d'un tableau, mais il permettrait un gain monumental
au niveau du temps de calcul non ? De toute façon, quelque soit la méthode que tu utiliseras, pour
determiner si un nombre n est premier, tu devras calculer dans tout les cas tout les nombres premiers
inferieurs à E(n/2) (en fait il s'agit de l'ensemble des nombres premiers inférieurs à la racine de n mais
comme tu l'as signalé, il est preferable en termes de performances d'éviter les opérations "exotiques")
et ça risque d'être (terriblement) gourmand en temps de calcul. Tu aurais donc tout interet à disposer
au minimum d'un tableau contenant les premiers nombres premiers tu gagnerais un temps fou sur les
nombres pas trop géants. Enfin bon, le sujet est vaste ... jete un coup d'oeil à ça si ça t'interesse (oui
c'est du pascal pour PC, mais que veux tu, moi aussi j'attends des compilo on-calc performant pour le
prototypage (à ce propos bon courage à tout les developpeurs de compilo on-calc (Thibault par exemple,
mais tout les autres aussi) ) ).

program n_primes;

uses Crt;

const MAX_SIZE = 8192;

type primes_array = array [1 .. MAX_SIZE] of LongInt;
primes_file = file of LongInt;

var primes : primes_array;
max_num : integer;

procedure init_results_array;
var i:integer;
begin
write('Initialising result''s array ...');
for i:=1 to max_num+1 do primes[i] := 0;
writeln(' done');
end;

function is_prime(n:longint):boolean;
var i:integer;
res : boolean;
begin
i:=1;
res := true;
while primes[i]<>0 do
begin
if n mod primes[i] = 0 then res := false;
i := i+1;
end;
is_prime:=res;
end;

procedure disp(var p : primes_array);
var i : integer;
begin
ClrScr;
for i:=1 to max_num do
begin
write(p[i]:8);
if i mod 8 = 0 then writeln;
if i mod 160 = 0 then
begin
writeln('Page ',i div 160,' on ',max_num div 160);
readln;
ClrScr;
end;
end;
readln;
ClrScr;
end;

procedure get_max_num;
begin
repeat
writeln('Please input a positiv number below ',MAX_SIZE,' :');
readln(max_num);
until (MAX_SIZE >= max_num) and (max_num >= 0);
end;

procedure calculate;
var i : integer;
n : LongInt;
begin
i := 1;
n := 2;
write('Start calculations ... you may go drink a(nother) coffee ...');
while i <= max_num do
begin
if is_prime(n) then
begin
primes[i] := n;
i := i + 1;
end;
n := n + 1;
end;
writeln(' done');
end;

procedure save(name:string);
var save_file : primes_file;
i : integer;
begin
assign(save_file,name);
rewrite(save_file);
write('Saving in file ',name,' ...');
for i:=1 to max_num do write(save_file,primes[i]);
writeln(' done');
close(save_file);
end;

procedure load(name:string);
var save_file : primes_file;
i : integer;
begin
i := 1;
assign(save_file,name);
reset(save_file);
write('Loading from file ',name,' ...');
while not eof(save_file) do
begin
read(save_file,primes[i]);
i := i + 1;
end;
max_num := i;
writeln(' done');
close(save_file);
end;

begin
ClrScr;
get_max_num;
init_results_array;
calculate;
disp(primes);
end.

L'utilisation du petit théoreme de fermat me semble relativement utilisable: ce théoreme donne des nombres probablement premiers.
Je cite: "Si P est premier et A non multiple de P, alors la division de A^(P-1) par P a pour reste 1.". A priori, l'avantage n'est pas évident, mais il à été prouvé recemment que tous les nombres inférieurs à 10^12, probablement (au sens du petit théoreme de Fermat) premiers dans les bases 2, 13, 23 et 1662803 le sont effectivement.
Le gain en calcul est alors evident

TiMad: jusqu'à 10^12 ça devrait te convenir, nan?

zewoo: je pense que cela demande beaucoup trop de resource systeme... en effet, les divisiopn avec reste, c'est pas ce qu'il y a de mieux..

desolé pour le double post

Non, il n'y a pas de problemes de ressources. Du moins pour les nombres assez grands.
Considerons un nombre n: avec la mùethode sqrt(n), il faudra tester tous les nombres premiers inferieurs à sqrt(n), pour n=16000000 environ cela fera environ 1000 division à efectuer (le millieme nombre premier est 15485863), avec ma methode, il n'en faudra que 4. Le gain en ressources est evident..
Pour ce qui est du crible, pour des nombre aussi grand, tu va t'amuser...

Erf en effet j'aivais pas lu ton poste jusqu'au bout

Ba moi j'en ait fait un avec des listes chainées :

librarie des noeuds :

struct tnoeud
{
float x;
struct tnoeud *suivant;
};

typedef struct tnoeud *Noeud;

struct tlist
{
int n;
Noeud tete;
};

typedef struct tlist List;

void createlist(List *l)
{
l->n = 0;
l->tete = (Noeud)NULL;
}

Noeud pointenoeud(List *l, int pos)
{
Noeud temp = l->tete;
int i;
for (i = 1; i < pos; i++) temp = temp->suivant;
return temp;
}

void addnoeud(List *l, float value)
{
Noeud temp = (Noeud)malloc(sizeof(Noeud));
temp->x = value;
temp->suivant = (Noeud)NULL;
if (l->n == 0) l->tete = temp;
else pointenoeud(l, l->n)->suivant = temp;
l->n = l->n + 1;
}


fonction pour les nombres 1ers :


void allnbr1er(List *listnbr1er, int a)
{
int nbr1er;
int i, j;
addnoeud(listnbr1er, 2);
for (i = 2; i < a+1; i++)
{
j = 1;
while ((nbr1er = (int)pointenoeud(listnbr1er, j)->x) < i && j < listnbr1er->n && i %nbr1er != 0) j++;
if (i % nbr1er != 0) addnoeud(listnbr1er, i);
}
}


La librarie de noeud permet aussi d'effacer certain noued, de libérer la mémoire et plein d'autres trucs mais la ca sert pas

Oui, ça fonctionne, mais essaye de l'implémenter avec une methode moins naive: eg utilisation du petit th de fermat
Le probleme ne venait pas trop du stockage des nombres premier, mais plutot de la lenteur de l'algo de recherche... De plus une allocation dynamique sur une 89/92+, c'est pas le top en matiére de performances.

renseigne toi sur la méthode Pollar-ro, c'est très efficace. (Pas dedétails ici, ça serait trops long)

Les listes chainées ne sont pas exploitable sur ti68k de maniere brute a cause du nbr de hdl limité.

Sinon pour le petit theoreme de fermat, je ne vois pas trop comment implenter un algorithme efficace

Les algo les plus rapide pour la recherche de nombres premiers sont les alogos probabilistes. Le plus connu est celui de Miller Rabin il te permet de déterminer très rapidement si un nombre est premier ou pas (mais pas d'en trouver le facteurs)

Idée d'un book d'algorithmique :
Utilisez des tableaux pour les listes chainées, et des indices de forme int plutôt que des pointeurs; ça gagne de la place, et c'est pas forcément plus lent (d'autant plus que le compilo C saura qu'il n'y a pas d'aliasing possible !)

Pour les allocations mémoires, il suffit de garder une liste des noeuds libres... c'est ce que j'utilise dans mon compilo COMA.

C'est pas une mauvaise idée mais dans ce cas je ne vois pas trop l'intéret d'une liste chainée. Pour ma part je les utilise pour avoir des tableaux dynamiques qui peuvant la moité de ces éléments puis dans la seconde en avoir 20 fois plus : un tableau dynamique quoi.
Avec ta technique il faudrait créer un tableau enorme qui se remplira et se desemplirai dynamiquement mais le probleme c'est que tu vas utiliser bcp de memoire pour rien....
Pour répondre à TiMad :
En ti68k tu peux faire des listes chainées mais de peu d'element c'est vrai, de meme tu peux faire des fonctions récursive mais elles ne doivent pas utiliser trop de mémoire ou bien faire peu de tour pour ne pas remplir la pile et avoir des erreurs a la con.
Ma technique permet juste d'utiliser tester tous les nombres entre deux bornes de maniere a savoir s'il ils sont 1ers ou pas en les divisants par uniquement par tous les nbr 1er inférieurs existant, il est donc en soit relativement efficace mais peut etre pas exploitable sur ti, je l'ai pas essayé.
Le fait est que je ne vois pas d'autre méthode réellemnt plus efficace puisque aucune eqution mathematique ne permet de dire si un nombre est 1er, tt du moins pour des grand nombres : le petit th de fermat marche pour peu de nombre je crois me souvenir.

IronMan a écrit :
C'est pas une mauvaise idée mais dans ce cas je ne vois pas trop l'intéret d'une liste chainée. Pour ma part je les utilise pour avoir des tableaux dynamiques qui peuvant la moité de ces éléments puis dans la seconde en avoir 20 fois plus : un tableau dynamique quoi. Avec ta technique il faudrait créer un tableau enorme qui se remplira et se desemplirai dynamiquement mais le probleme c'est que tu vas utiliser bcp de memoire pour rien....

Euh, tu connais realloc?

"Le fait est que je ne vois pas d'autre méthode réellemnt plus efficace puisque aucune eqution mathematique ne permet de dire si un nombre est 1er, tt du moins pour des grand nombres "

Eh bien si, les algorithmes probabilistes!
regardez mon post plus haut (#12)!

pour répondre à Kevin Kofler, bien sur que je connais realloc, mais c'est vrai que je ne connais pas assez bien les compilateurs pour savoir si il est plus efficace de faire des realloc avec un tableau que de faire des listes chainée et je trouve les principe des listes chainées assez sympas pour faire des tableaux dynamiques genre la liste des tirs d'un gusgus dans un jeu ou autre (faut m'excuser).
pour repondre a The_beast, le fait est qu'il n'existe aucune formule qui permet de savoir si un nombre est premier ou pas, les algos probabilistes, je suppose, teste si un nombre est divisble par des nombres 1er plus ou moins probable, ou bien teste d'autre propriétées des nombres. S'il existe des equations qui decrivent les nbrs 1er alors je me demande pq des mathematiciens cherchent tjs les nbr 1er les plus gds?

ps : Kevin kofler pourrai tu m'eclairer sur l'utilité alors des listes chainées?

IronMan
a écrit : pour répondre à Kevin Kofler, bien sur que je connais realloc, mais c'est vrai que je ne connais pas assez bien les compilateurs pour savoir si il est plus efficace de faire des realloc avec un tableau que de faire des listes chainée et je trouve les principe des listes chainées assez sympas pour faire des tableaux dynamiques genre la liste des tirs d'un gusgus dans un jeu ou autre (faut m'excuser).

Sur PC, les listes chaînées sont plus efficaces normalement.
Sur TI-89/92+, le realloc (ou mieux, HeapRealloc avec toutes les fonctions Heap* à base de HANDLEs qui vont avec) convient mieux.

"il n'existe aucune formule qui permet de savoir si un nombre est premier ou pas"
->FAUX c'est précisement le role des algos probalistes
Un algorithme probabiliste te dis avec un certaine certitude (élevé donc tu est sur) si un nombre est premier ou pas. Ce que ne fait pas un tel algorithme c'est de donner les facteurs.

>> je me disais bien aussi que les listes chainées deviaent bien servir a qqchose. De tte maniere, mon algo n'etait pas optimisé pour les ti comme je l'ai dit dans mon 1er post, je l'avais fait pour PC. C clair que sur TI tt ce qui est recursif n'est pas aidé vu la taille de la pile.

>> pourrais tu me dire the_beast comment fonctionne un algo probabiliste? Parce qu'un algo comme le mien ne donne qu'un seul des facteurs ce qui permet d'etre sur qu'il n'est pas 1er puisqu'il a un factuer qui n'est ni un ni lui meme.

C'est la magie des algo probabilste, on sait si un nombre est premier ou pas sans en trouver un seul facteur. Il y en a deux types: ceux dont on est sur qu'un nombre est premier (et donc peut etre factorisable ceux-ci sont bcp plus longs), et ceux dont on est sure qu'un nombre est factorisable.

Voici l'exemple de l'algo de Miller-Rabin
(écrit par moi en basic)

function isprim(n)
d=3
for d=3 to 41 step 2
if n-INT(n/d)*d=0 then
"Non premier"
goto [fin]
end if
next d
r=(n-1)/2
e=1
j=0
for i= 1 to 5
a=INT(RND(1)*(n-4))+2
y=mod2(a,r,n)
if y<>1 and y<>n-1 then
j=1
while j<r and y<>n-1
y=mod(y*y,n)
if y=1 then
"Non premier"
goto [fin]
end if
j=j+1
if y<>n-1 then
"Non premier"
goto [fin]
end if
wend
end if
next i
"Surement premier"
[fin]
end function
mod(a,b) est le modulo (le reste de a par b)
mod2(a,b,c) est: modulo (a^b,c)
INT est la partie entière
Cet algo fonctionne tjs parfaitement avec des nombres de 231 chiffres
Ces algorithme font appel a des test (évidemment) et à des calculs de modulo (reste)

Erf je comprend rien a ton algo

function isprim(n)  d=3  for d=3 to 41 step 2  if n-INT(n/d)*d=0 then  "Non premier"  goto [fin]  end if  next d  r=(n-1)/2  e=1  j=0  for i= 1 to 5  a=INT(RND(1)*(n-4))+2  y=mod2(a,r,n)  if y<>1 and y<>n-1 then  j=1  while j<r and y<>n-1  y=mod(y*y,n)  if y=1 then  "Non premier"  goto [fin]  end if  j=j+1  if y<>n-1 then  "Non premier"  goto [fin]  end if  wend  end if  next i  "Surement premier"  [fin]  end function 

C'est mieux comme ca peut etre

Merde, il manque plein de mots clés...
Quoique c'est juste de l'algo, faudrait peu etre rajouter un langage pur algo!

C'est du QBASIC, donc c'est normal qu'il n'y a pas tous les mots-clés quand on fait de la coloration TI-BASIC. Ceci dit, il en faudrait une pour le QBASIC...

J'en connais un à ki ça plairait en effet

Ben pour faire un algo probabiliste en tibasic, y a ca : premier(n) Func return isprime(n) EndFunc

Nan plus sérieusement, la fonction isprime en basic est probabiliste, il suffit juste de demander la source à WormHole

Mon algo n'est pas en Qbasic mais ca y ressemble beaucoup.
La 89 inclus effectivement une fonction probabiliste pour savoir si un nombre premier: ISPRIME(n) ou ESTPREM(n)
Et pour factoriser un nombre FACTOR(n)

au faite #pub# si tu es interessé par les recherches approchées de nombres premiers y'a un pti passage sur mon tuto#pub#