Nombres premiers...

dcdc2

25/08/2004 à 18:40

La liste et la limite étant de faible taille,
l'objet n'étant pas de d'optimiser quoi que ce soit

le mieux est sans doute de parcourir (boucle) la liste des entiers, en
regardant s'il est divisible par un des précédents 'premier' trouvé. S'il ne
l'est pas, alors on l'ajoute à la liste des nombres connus premiers.

Dans un tableau ? dans des cellules ? sans grande importance à cette
échelle.
pense à débuter par 2, sinon tout le monde sera divisible par 1

François Picalausa

25/08/2004 à 19:32

Hello,

Voici un exemple pour cette approche simple, très simple... trop simple que
pour être rapide...

'Dans un form avec une listbox list1
Dim Num As Long
Dim Div As Long
Dim Pri() As Long
Dim bIsPri As Boolean

Const MAX_NUM = 100 'jusqu'a 100
ReDim Pri(0)

List1.AddItem 2

Pri(0) = 3
List1.AddItem 3

'Boucle sur les nombres.
'Pour gagner du temps,
'on exclu les multiples de 2 (Step 2)
'Le premier connu est 3
' 4 n'est pas un premier
'donc on commence à 5
For Num = 5 To MAX_NUM Step 2
Div = 0 'on commence à l'index 0 du tableau
bIsPri = True 'on présuppose que le nombre est premier

'On divise le nombre par tous
'les nombres premiers le précédent.
'(si on trouve que le nombre peut être divisé
'on arrête la boucle)
Do While (Div <= UBound(Pri) And bIsPri)
bIsPri = (Num Mod Pri(Div))
Div = Div + 1 'index suivant du tableau
Loop

If bIsPri Then 'si le nombre est premier
'on l'ajoute au tableau
ReDim Preserve Pri(UBound(Pri) + 1)
Pri(UBound(Pri)) = Num
'et à la liste
List1.AddItem Num
End If
Next Num

Il y a certainement moyen d'optimiser ce bout de code (emploi de tableaux
statiques par exemple)... mais la méthode restera lente.
Voici un site qui décrit des méthodes plus optimisées:
http://membres.lycos.fr/villemingerard/Premier/testprim.htm

--
François Picalausa (MVP VB)
http://faq.vb.free.fr --- http://msdn.microsoft.com

"dcdc2" a écrit dans le message
de news:

le mieux est sans doute de parcourir (boucle) la liste des entiers,
en regardant s'il est divisible par un des précédents 'premier'
trouvé. S'il ne l'est pas, alors on l'ajoute à la liste des nombres
connus premiers.

Jean-Marc

25/08/2004 à 21:36

"Toine" a écrit dans le message de
news:cgicjn$cv0$

Bonjour,

Lors d'un entretien d'embauche, on m'a demandé d'écrire un algorithme
permettant de trouver les 100 premiers nombres premiers... et à ma grande
honte, je n'ai pas su le faire.
Et même à tête reposée, je n'y arrive pas, alors je sollicite votre aide.
Attention, je parle d'un truc simple, pas de se servir de fonctions
mathématiques permettant d'optimiser la recherche de nombres premiers
supérieurs à X^12. Ca, j'en ai trouvé plein sur le net, mais àa m'a pas
beaucoup avancé :)

Question subsidaire: sur quel forum poster ce genre de questions ? J'ai
posté ici parceque je dois écrire le programme en VB, mais je suppose

qu'il

y'a un forum plus approprié.

Hello,

1/ c'est une question type, pour évaluer si un candidat à les bases en
algorithmique.
En général, on demande ça, ou un tri à bulle, ou encore 3 façons de coder la
factorielle.

Remarque: dans le cas des 100 premiers nombres premiers, j'attend d'un
candidat qu'il
implémente un crible d'eratosthene. Si il ne connait pas (ça peut arriver,
si il a eu des profs qui n'en étaient pas...) alors je lui donne les specs
(dans ce cas, la description en anglais de l'algorithme) et le test consiste
alors à implémenter les specs en question.

Remarque 2: Ce genre d'algo s'implémente en 10 minutes en n'importe quel
langage évolué.

2/ Le forum pour parler de cela est: fr.comp.algorithmes

Jean-marc

JeanPaul

26/08/2004 à 09:32

Voici un mini programme que j'avais trouvé.(Il faut 2 TextBox et un Bouton)

Option Explicit
Private Sub Command1_Click()
Dim a, b, c As Long
Dim d As Integer
' a = nombre de nombres premiers choisis
' b = nombre à tester
' d = compteur de nombre

b = 1: d = 0
a = Val(Text1.Text)
Text1.Text = "" ' Vide l'écran du choix
début:
b = b + 2
If d >= a Then GoTo fin
For c = 2 To Sqr(b)
If b Mod c = 0 Then GoTo début
Next c
' b est premier
Text2.Text = Text2.Text & Str(b) & vbCrLf
d = d + 1
GoTo début

fin:
MsgBox "Liste générée", vbOKOnly + vbInformation, "Voila !"
End Sub

Private Sub Text1_KeyPress(KeyAscii As Integer)
'Autorise seulement la saisie des chiffres
If KeyAscii < 48 Or KeyAscii > 57 Then
KeyAscii = 0
Beep
MsgBox "Que des chiffres !", vbOKOnly + vbInformation, "Attention!"
End If
End Sub

Jean Paul

Toine

26/08/2004 à 10:58

Merci à tous, je vais potasser tout ceci... pour mon prochain entretien :)

"Toine" a écrit dans le message de news:
cgicjn$cv0$

Bonjour,

Lors d'un entretien d'embauche, on m'a demandé d'écrire un algorithme
permettant de trouver les 100 premiers nombres premiers... et à ma grande
honte, je n'ai pas su le faire.
Et même à tête reposée, je n'y arrive pas, alors je sollicite votre aide.
Attention, je parle d'un truc simple, pas de se servir de fonctions
mathématiques permettant d'optimiser la recherche de nombres premiers
supérieurs à X^12. Ca, j'en ai trouvé plein sur le net, mais àa m'a pas
beaucoup avancé :)

Question subsidaire: sur quel forum poster ce genre de questions ? J'ai
posté ici parceque je dois écrire le programme en VB, mais je suppose
qu'il y'a un forum plus approprié.

Merci d'avance pour vos lumières

Vincent Guichard

26/08/2004 à 11:05

Toine a écrit :

Bonjour,

Lors d'un entretien d'embauche, on m'a demandé d'écrire un algorithme
permettant de trouver les 100 premiers nombres premiers... et à ma grande
honte, je n'ai pas su le faire.
Et même à tête reposée, je n'y arrive pas, alors je sollicite votre aide.
Attention, je parle d'un truc simple, pas de se servir de fonctions
mathématiques permettant d'optimiser la recherche de nombres premiers
supérieurs à X^12. Ca, j'en ai trouvé plein sur le net, mais àa m'a pas
beaucoup avancé :)

Question subsidaire: sur quel forum poster ce genre de questions ? J'ai
posté ici parceque je dois écrire le programme en VB, mais je suppose qu'il
y'a un forum plus approprié.

Merci d'avance pour vos lumières

Tu as un exemple d'implémentation du crible d'Erathostène en pseudo-code
à cet endroit:
http://www.chez.com/algor/math/eratho.htm

L'adapter en VB ne devrait pas être très dur.

Vincent Guichard

ng

26/08/2004 à 20:26

Salut,

Dim a, b, c As Long

Attention on est pas en VB.Net ! Ici a et b seront en variant et non
long, on utilise donc cette syntaxe :
Dim a As long, b as long, c as long

JeanPaul a exprimé avec précision :

Dim a, b, c As Long

--
Nicolas G.
FAQ VB : http://faq.vb.free.fr
API Guide : http://www.allapi.net
Google Groups : http://groups.google.fr/
MZ-Tools : http://www.mztools.com/

Patrice Henrio

26/08/2004 à 22:08

En fait, au niveau de l'entretien, je pense qu'on a voulu surtout tester les
connaissances du candidat car une fois que l'on sait ce qu'est un nombre
premier et que l'on sait un minimum programmer on peut le réaliser dans
n'importe quel langage.
Donc un nombre premier est un nombre entier qui a exactement deux diviseurs,
un et lui-même.

Un nombre a est divisible par un nombre b si le reste de la division entière
de a par b est 0.

a divise b alors a<=b.

Avec tout cela on peut lancer l'algorithme.

Public NbPremier as byte
Public Premiers[1 to 100] as integer
sub main()
NbPremier=1
N=2
while NbPremier < 100
If Premier(N) then
NbPremier=NbPremier+1
Premiers[NbPremier]=N
End If
wend
end sub

Function Premier(N as integer) as boolean
Dim resultat as boolean, X as integer
resultat= (N=2)
X=3
do
resultat = ((N mod X)=0)
X=X+2
loop until resultat or (X>=N)
Premier=resultat
end function

Une amélioration est obtenue grâce au théorème suivant : si a est non
premier, alors a admet un diviseur inférieur ou égal à la racine carrée de a

on ré-écrit premier ainsi

Function premier(N as integer) as boolean
dim resultat as boolean, X as integer
resultat=(N=2)
X=3
do
resultat=((N mod X)=0)
X=X+2
loop until resultat or (X*X >= N)
premier = resultat
end function

autre amélioration liée à un autre théorème : si a est non premier, alors il
admet un diviseur premier inférieur à la racine carrée de a

donc

Function premier(N as integer) as boolean
dim resultat as boolean, X as integer
resultat=(N=2)
If Not Resultat
I=1
do
X=Premiers[I]
resultat=((N mod X)=0)
I=I+1
loop until resultat or (X*X>=N) or (I > NbPremiers)
end if
premier = resultat
end function

Voilà.

Je pense que c'est l'une de ses solutions qu'attendait le jury.

Je n'ai pas testé, donc il peut y avoir des erreurs de frappe, par contre je
garantis le raisonnement (je suis agrégé de math depuis vingt ans et j'ai
enseigné l'informatique pendant dix ans).

"ng" a écrit dans le message de
news:

Salut,
>Dim a, b, c As Long
Attention on est pas en VB.Net ! Ici a et b seront en variant et non
long, on utilise donc cette syntaxe :
Dim a As long, b as long, c as long

JeanPaul a exprimé avec précision :
> Dim a, b, c As Long

--
Nicolas G.
FAQ VB : http://faq.vb.free.fr
API Guide : http://www.allapi.net
Google Groups : http://groups.google.fr/
MZ-Tools : http://www.mztools.com/

En fait, au niveau de l'entretien, je pense qu'on a voulu surtout tester les
connaissances du candidat car une fois que l'on sait ce qu'est un nombre
premier et que l'on sait un minimum programmer on peut le réaliser dans
n'importe quel langage.
Donc un nombre premier est un nombre entier qui a exactement deux diviseurs,
un et lui-même.

Un nombre a est divisible par un nombre b si le reste de la division entière
de a par b est 0.

a divise b alors a<=b.

Avec tout cela on peut lancer l'algorithme.

Public NbPremier as byte
Public Premiers[1 to 100] as integer
sub main()
NbPremier=1
N=2
while NbPremier < 100
If Premier(N) then
NbPremier=NbPremier+1
Premiers[NbPremier]=N
End If
wend
end sub

Function Premier(N as integer) as boolean
Dim resultat as boolean, X as integer
resultat= (N=2)
X=3
do
resultat = ((N mod X)=0)
X=X+2
loop until resultat or (X>=N)
Premier=resultat
end function

Une amélioration est obtenue grâce au théorème suivant : si a est non
premier, alors a admet un diviseur inférieur ou égal à la racine carrée de a

on ré-écrit premier ainsi

Function premier(N as integer) as boolean
dim resultat as boolean, X as integer
resultat=(N=2)
X=3
do
resultat=((N mod X)=0)
X=X+2
loop until resultat or (X*X >= N)
premier = resultat
end function

autre amélioration liée à un autre théorème : si a est non premier, alors il
admet un diviseur premier inférieur à la racine carrée de a

donc

Function premier(N as integer) as boolean
dim resultat as boolean, X as integer
resultat=(N=2)
If Not Resultat
I=1
do
X=Premiers[I]
resultat=((N mod X)=0)
I=I+1
loop until resultat or (X*X>=N) or (I > NbPremiers)
end if
premier = resultat
end function

Voilà.

Je pense que c'est l'une de ses solutions qu'attendait le jury.

Je n'ai pas testé, donc il peut y avoir des erreurs de frappe, par contre je
garantis le raisonnement (je suis agrégé de math depuis vingt ans et j'ai
enseigné l'informatique pendant dix ans).

"ng" <ng@ngsoft-fr.com> a écrit dans le message de
news:mn.d4ca7d4825e4cb33.17432@ngsoft-fr.com...

Salut,
>Dim a, b, c As Long
Attention on est pas en VB.Net ! Ici a et b seront en variant et non
long, on utilise donc cette syntaxe :
Dim a As long, b as long, c as long

JeanPaul a exprimé avec précision :
> Dim a, b, c As Long

--
Nicolas G.
FAQ VB : http://faq.vb.free.fr
API Guide : http://www.allapi.net
Google Groups : http://groups.google.fr/
MZ-Tools : http://www.mztools.com/

Vous avez filtré cet utilisateur ! Consultez son message

En fait, au niveau de l'entretien, je pense qu'on a voulu surtout tester les
connaissances du candidat car une fois que l'on sait ce qu'est un nombre
premier et que l'on sait un minimum programmer on peut le réaliser dans
n'importe quel langage.
Donc un nombre premier est un nombre entier qui a exactement deux diviseurs,
un et lui-même.

Un nombre a est divisible par un nombre b si le reste de la division entière
de a par b est 0.

a divise b alors a<=b.

Avec tout cela on peut lancer l'algorithme.

Public NbPremier as byte
Public Premiers[1 to 100] as integer
sub main()
NbPremier=1
N=2
while NbPremier < 100
If Premier(N) then
NbPremier=NbPremier+1
Premiers[NbPremier]=N
End If
wend
end sub

Function Premier(N as integer) as boolean
Dim resultat as boolean, X as integer
resultat= (N=2)
X=3
do
resultat = ((N mod X)=0)
X=X+2
loop until resultat or (X>=N)
Premier=resultat
end function

Une amélioration est obtenue grâce au théorème suivant : si a est non
premier, alors a admet un diviseur inférieur ou égal à la racine carrée de a

on ré-écrit premier ainsi

Function premier(N as integer) as boolean
dim resultat as boolean, X as integer
resultat=(N=2)
X=3
do
resultat=((N mod X)=0)
X=X+2
loop until resultat or (X*X >= N)
premier = resultat
end function

autre amélioration liée à un autre théorème : si a est non premier, alors il
admet un diviseur premier inférieur à la racine carrée de a

donc

Function premier(N as integer) as boolean
dim resultat as boolean, X as integer
resultat=(N=2)
If Not Resultat
I=1
do
X=Premiers[I]
resultat=((N mod X)=0)
I=I+1
loop until resultat or (X*X>=N) or (I > NbPremiers)
end if
premier = resultat
end function

Voilà.

Je pense que c'est l'une de ses solutions qu'attendait le jury.

Je n'ai pas testé, donc il peut y avoir des erreurs de frappe, par contre je
garantis le raisonnement (je suis agrégé de math depuis vingt ans et j'ai
enseigné l'informatique pendant dix ans).

"ng" a écrit dans le message de
news:

Salut,
>Dim a, b, c As Long
Attention on est pas en VB.Net ! Ici a et b seront en variant et non
long, on utilise donc cette syntaxe :
Dim a As long, b as long, c as long

JeanPaul a exprimé avec précision :
> Dim a, b, c As Long

--
Nicolas G.
FAQ VB : http://faq.vb.free.fr
API Guide : http://www.allapi.net
Google Groups : http://groups.google.fr/
MZ-Tools : http://www.mztools.com/

GuY - TouTenN

26/08/2004 à 23:36

> Tu as un exemple d'implémentation du crible d'Erathostène en pseudo-code
à cet endroit:
http://www.chez.com/algor/math/eratho.htm

Voilà le code traduit en VB... si ça peut faire avancer le shimimili.... le
chimulibic... le chumbike.... le "crible d'Erathostène"

En espérant qu'il aura le boulot.....

'une Form, une listbox et un commandbutton
Private Sub Command1_Click()
N = 1000
Dim A(1000)
For i = 1 To N
A(i) = True
Next i
M = Fix(Sqr(N))
For i = 2 To M
If A(i) = True Then
For j = 2 To N / i
A(i * j) = False
Next j
End If
Next i
tot = 0
For i = 1 To N
If A(i) = True And i <> 1 Then tot = tot + 1: List1.AddItem i
If tot = 100 Then Exit For
Next i
MsgBox tot
End Sub

--
GuY - TouTen N

Pascal

10/09/2004 à 16:15

Toine wrote:

Bonjour,

Lors d'un entretien d'embauche, on m'a demandé d'écrire un algorithme
permettant de trouver les 100 premiers nombres premiers... et à ma grande
honte, je n'ai pas su le faire.
Et même à tête reposée, je n'y arrive pas, alors je sollicite votre aide.
Attention, je parle d'un truc simple, pas de se servir de fonctions
mathématiques permettant d'optimiser la recherche de nombres premiers
supérieurs à X^12. Ca, j'en ai trouvé plein sur le net, mais àa m'a pas
beaucoup avancé :)

Question subsidaire: sur quel forum poster ce genre de questions ? J'ai
posté ici parceque je dois écrire le programme en VB, mais je suppose qu'il
y'a un forum plus approprié.

Merci d'avance pour vos lumières

Ba c'est pas très dur. En quelque ligne, suffit juste de se rappeler
qu'un nombre premier n'est divisible que par lui même et un. Commencer à
partir de 2 (un n'est pas premier...) pour être rigoureux. Après il
existe déjà de nombreux algorithmes, mais le plus simple reste celui la.
X : nb a trouver
i, j: deux var

x = 2
Tant que X <100 faire
pour i = 2 to X-1 faire
si x div i = 0 print X
next i
x=x+1
fin tant que

--
Pascal

Nombres premiers...

10 réponses

Veuillez sélectionner un problème