Algorithme pour trouver les nombres premiers

[invitedf3b174e]

Bonjour

Je commence par une description naïve avant de développer l’algorithme analytiquement.

On pose tous les nombres premiers dans de petites boite sur une ligne allant vers l’infinie. On ne prend pas le 1 et le 2 car ils sont premiers par définition.
La boite 1 contient le 3, la boite 2 le 4, la boite 3 le 5 et ainsi de suite ….

On commence l’algorithme

Une première personne commence.
Elle prend la première boite et la remet avec le nombre qu’elle contienne (c‘est le 3) à monsieur RNP « ramasseur des nombres premiers ».
Elle ouvre les boites restantes, une boite sur 2,
la première boite qui est devant elle (contient le nombre 4) la jette dans la poubelle
la 2eme boite (contient le nombre 5) elle la saute
la 3eme boite (contient le nombre 6), elle l’ouvre prend le nombre qu’elle contient et remet le boite vide à sa place
la 4eme boite (contient le nombre 7) elle la saute (il procède une sur deux)
la 5eme boite (contient le nombre 8), elle l’ouvre prend le nombre qu’elle contient et remet le boite vide à sa place
…. Et elle continue ainsi sans s’arrêter
Ainsi on aura au sol, les boites contenant les nombres : 5, vide, 7, vide, 9, vide, 11, vide, 13, vide, 15, ……,

Une deuxième personne prend le relai et fait exactement la même chose mais cette fois elle ouvre les boites une sur 3 (elle a un pas plus allongé que la personne précédente).
Elle prend la première boite et la remet avec le nombre qu’elle contienne (c‘est le 5) à monsieur RNP « ramasseur des nombres premiers ».
Elle ouvre les boites restantes, une boite sur 3,
la première boite qui est devant elle (elle est vide) la jette dans la poubelle
la 2eme boite (contient le nombre 7) et la 3eme boite (vide), elle les sautes
la 4eme boite (contient le nombre 9), elle l’ouvre prend le nombre qu’elle contient et remet le boite vide à sa place
…. Et elle continue ainsi sans s’arrêter
Ainsi on aura au sol, les boites contenant les nombres : 7, vide, vide, vide, 11, vide, 13, vide, vide, vide, 17,

La 3eme personne à un pas plus allongé et elle ouvre les boites une sur 4,
Si vous vérifiez vous allez trouver que :
Elle remet la boite contenant le 7 à monsieur RNP
Elle ne trouvera que les boites vides

Ceci est un algorithme, mais comment le transformer en analytique
-----

[choom]

Bonjour

...
Ceci est un algorithme, mais comment le transformer en analytique

Bonsoir.

Que veux-tu dire exactement par «*transformer en analytique*» ?

Est-ce décrire formellement en langage mathématique ces opérations effectuées sur les nombres entiers, ainsi que le résultat obtenu ( à condition de s’imposer une limite à sa promenade, car l’infini c’est loin ...) ?

Nb: c’est une version perso d’un crible connu depuis l’antiquité.

Bien cordialement,
Choom

[pm42]

Nb: c’est une version perso d’un crible connu depuis l’antiquité.

En effet : https://fr.wikipedia.org/wiki/Crible_d%27Ératosthène. Et ce n'est pas pratique pour trouver des grands nombres premiers qui est ce qu'on cherche.

[invitedf3b174e]

En effet : https://fr.wikipedia.org/wiki/Crible_d%27Ératosthène. Et ce n'est pas pratique pour trouver des grands nombres premiers qui est ce qu'on cherche.

BONJOUR
En réalité je ne sais pas ce que je veux,
Je m’amuse c’est tout

J’utilise l’EXCEL pour trouver les nombre premier en procédant par criblage, ceci ne pourra s’appeler qu’algorithme.
J’écris tous les nombres du 2 à N.
Je mets dans le panier des nombres premiers le premier nombre de la liste (c’est le 2)
Je supprime tous les nombres multiples de 2 mais sans utiliser les calculs en les supprimant un nombre sur 2
Il me reste unique les nombres impairs, et je mets dans le panier le nombre 3
Je vais procéder ensuit à l’élimination des multiple de 3 et je remarque que le premier multiple de 3 qui reste dans la liste est le carré du 3 et je prends tous les nombres inférieur à ce carré (le 5 et le 7 ) et je les met dans le panier. Nom panier des nombres premier contient (2, 3, 5 et 7)
Pour supprimer les multiple de 3, sans utiliser les calcule, je constate qu’ils sont répartis 1 sur 3, ils sont facilement repérables : 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25, 27, 29, 31, 33, 35, 37, 39, 41, 43, 45, 47, 49, 51, 53, 55,
Il reste dans la liste les nombres suivants : 11, 13, 17, 19, 23, 25, 29, 31, 35, 37, 41, 43, 47, 49, 53, 55, 59, 61, 65, 71, 73, 77, 79, 83, 85
je mets dans le panier le nombre 11 (premier nombre de la liste)
Je procède ensuit à l’élimination des multiple de 5 (c’est le nombre premier qui suit le 3 dans le panier)
Le premier multiple est le 25, le carré de 5 et comme précédemment pour le 3 je prends tous les nombres inferieur à ce carré et je les mets dans le panier (2, 3, 5, 7, 11, 13, 17, 19 et 23), mon panier grandit rapidement
Pour supprimer les multiple de 5 sans utiliser les calcule je constate qu’ils sont répartis uniformément ; je supprime le premier, je saute 2 nombres et je supprime le suivant puis je saute 6 et je reviens à sauter puis 6 puis 2 puis 6 (je note pour le nombre 5 la répartition (2 , 6))
25, 29, 31, 35, 37, 41, 43, 47, 49, 53, 55, 59, 61, 65, 71, 73, 77, 79, 83, 85

Maintenant pour le 7
En résumé les nombres inférieurs au carré de 7 (49) sont à mettre dans le panier (29, 31, 37, 41, 43, 47)
Pour supprimer les multiples de 7 la répartition est (6 , 3)
Pour les multiples de de 11 la répartition est (3 , 5)
Pour les multiples de de 13 la répartition est (8 , 6)

En connaissant la répartition des nombres premiers, la création d’un programme deviendra facile

En arrivant à 13 soit 5 opération j’ai dans le panier 60 nombre premier

[A voir en vidéo sur Futura]

[invite51d17075]

reste que tu ré écris ( en plus compliqué ) ce qui a été déjà proposé dès l'antiquité.

[invitedf3b174e]

reste que tu ré écris ( en plus compliqué ) ce qui a été déjà proposé dès l'antiquité.

Bonsoir
Je ne sais pas ce qui a était dit au sujet de la recherche des nombres premiers à l'antiquité. Ce n’était pas dans les cours.

Je cherche une méthode (la plus simple) avec les moyens d'aujourd’hui

[invite51d17075]

ici :
https://fr.wikipedia.org/wiki/Crible...atosth%C3%A8ne
( III siècle A JC)
et une version améliorée bien plus récente ( et plus complexe )
https://fr.wikipedia.org/wiki/Crible_d%27Atkin

[pm42]

https://fr.wikipedia.org/wiki/Crible...atosth%C3%A8ne

Le lien a été donné dès le 3ème message.
Bon courage parce que je ne sens pas ici une volonté d'apprendre, juste de réinventer la roue en la faisant carrée.

[albanxiii]

Je ne sais pas ce qui a était dit au sujet de la recherche des nombres premiers à l'antiquité. Ce n’était pas dans les cours.

Ceci n'est pas une justification acceptable, sauf à votre paresse intellectuelle.
Heureusement que tout le monde ne raisonne pas de cette façon, sinon on serait encore dans des grottes avec des peaux de bêtes sur le dos.

(la prochaine fois que mon chef trouvera que mon travail n'avance pas assez vite, je lui sortirai cet argument, on verra bien )

[invite51d17075]

Le lien a été donné dès le 3ème message.

oui, exact ! désolé pour la redite sans citation.....
j'en rajoute un autre bien plus complexe, pour exciter les neurones, mais il n'a certainement pas été vu en cours.

[invite6486d7bd]

Heureusement que tout le monde ne raisonne pas de cette façon, sinon on serait encore dans des grottes avec des peaux de bêtes sur le dos.

Heureusement que certains raisonnent de cette façon (essayer par soi-même avant de copier sur le voisin), sinon on serait encore dans des grottes avec des peaux de bêtes sur le dos...

[Deedee81]

Salut,

Bon, c'est quand même mieux que d'être dans des peaux de bêtes avec des grottes sur le dos

[Olivzzz]

Salut,

Bon, c'est quand même mieux que d'être dans des peaux de bêtes avec des grottes sur le dos

C'est pas très gentil de se moquer ainsi des tortues !

[vgondr98]

Bonjour, comme je me s'y mis à la programmation avec R, je viens d'écrire un programme permettant d'afficher la liste des nombres premiers jusqu'à N.

 Cliquez pour afficher

N <- 1000
Nboolvector = FALSE

for ( i in seq(1,N + 1,1)) {

	if(i == 1) {
	
		Nboolvector[i] = TRUE
		
	} else if(i == 2) {
	
		Nboolvector[i] = TRUE
		
		for (j in seq(i,N + 1,i)) {
		
			j = j + 2

			if(j < N + 1) {

				Nboolvector[j] = FALSE
				
			} else {
			
			}
			
		}
		
	} else if(is.na(Nboolvector[i]) == TRUE) {
	
		Nboolvector[i] = TRUE
		
		for (k in seq(i,N + 1,i)) {
		
			k = k + i

			if(k < N + 1) {
			
				Nboolvector[k] = FALSE
				
			} else {
			
			}
			
		}
		
	} else if(i == N){
	
		break;
	
	}
	
}

vecteur <- 1

for (i in seq(2,N + 1,1)) {
	
	if(is.na(Nboolvector[i])) {
	
	} else if (Nboolvector[i] == TRUE) {
	
		vecteur <- c(vecteur,i)
		
	}
	
}
vecteur

[invitedf3b174e]

Bonjour, comme je me s'y mis à la programmation avec R, je viens d'écrire un programme permettant d'afficher la liste des nombres premiers jusqu'à N.

 Cliquez pour afficher

N <- 1000
Nboolvector = FALSE

for ( i in seq(1,N + 1,1)) {

	if(i == 1) {
	
		Nboolvector[i] = TRUE
		
	} else if(i == 2) {
	
		Nboolvector[i] = TRUE
		
		for (j in seq(i,N + 1,i)) {
		
			j = j + 2

			if(j < N + 1) {

				Nboolvector[j] = FALSE
				
			} else {
			
			}
			
		}
		
	} else if(is.na(Nboolvector[i]) == TRUE) {
	
		Nboolvector[i] = TRUE
		
		for (k in seq(i,N + 1,i)) {
		
			k = k + i

			if(k < N + 1) {
			
				Nboolvector[k] = FALSE
				
			} else {
			
			}
			
		}
		
	} else if(i == N){
	
		break;
	
	}
	
}

vecteur <- 1

for (i in seq(2,N + 1,1)) {
	
	if(is.na(Nboolvector[i])) {
	
	} else if (Nboolvector[i] == TRUE) {
	
		vecteur <- c(vecteur,i)
		
	}
	
}
vecteur

Bonsoir
Écrire sous forme informatique un algorithme c'est banale.
Il faut d'abord trouver l'algorithme.
Tu procédera comment pour trouver les nombres premiers
Si tu dis que je prend un nombre et je le divise pour voir s'il est premier alors c'est pas la peine de continuer

[pm42]

Bonsoir
Écrire sous forme informatique un algorithme c'est banale.
Il faut d'abord trouver l'algorithme.
Tu procédera comment pour trouver les nombres premiers
Si tu dis que je prend un nombre et je le divise pour voir s'il est premier alors c'est n'est pas peine de continuer

Il a justement implémenté un crible.
Je ne sais pas trop quoi dire : entre le très, très faible niveau de ce que tu as présenté (et je suis gentil), ton refus d'apprendre et maintenant, le besoin de déprécier ce qu'à fait quelqu'un d'autre, il est difficile de te parler en restant des les limites de la charte et de la politesse.

[invitedf3b174e]

Bonsoir
Je ne sais pas ce qui a était dit au sujet de la recherche des nombres premiers à l'antiquité

Correction
Je ne sais pas ce qui a été dit au sujet de comment trouver tous les nombres premiers,
À ce jour on sait pas le faire

[invite51d17075]

ce n'est certainement pas avec ton approche qu'on en prend le chemin.
car comme toutes les autres ( plus ou moins sophistiquées ) , elle conduit à les lister au fur et à mesure.
et encore une fois , c'est une sous version de l'approche la plus ancienne.

[invite6486d7bd]

Vous me donnez n'importe quel nombre, je vous dis s'il est premier.
(C'est une astuce mais bon je ne suis pas mathématicien...)

[Deedee81]

Salut,

Vous me donnez n'importe quel nombre, je vous dis s'il est premier.
(C'est une astuce mais bon je ne suis pas mathématicien...)

Je crois que j'ai deviné

Concernant le sujet, une question fort intéressante n'est pas tant d'avoir un algorithme qui donne les nombres premiers, ça c'est assez facile, mais d'avoir des algorithmes efficaces pour tester si un grand nombre est premier. Il y a pas mal de littérature sur le net à ce sujet.

[vgondr98]

Il y a pas mal de littérature sur le net à ce sujet.

http://villemin.gerard.free.fr/Wwwgv...r/testprim.htm

[invite6486d7bd]

http://villemin.gerard.free.fr/Wwwgv...r/testprim.htm

Non, mais c'est trop facile ça (Le boulot est déjà fait, il suffit de suivre le mode d'emploi ).

[invite51d17075]

c'est juste.
mais comme ce sujet est une marotte pour beaucoup de mathématiciens depuis fort longtemps, il n'est pas étonnant qu'il ait déjà fait couler beaucoup d'encre.
faire du nouveau sur le sujet n'est donc pas chose aisée.
de fait, on "améliore" à chaque fois un peu plus l'optimisation......

Je ne sais pas ce qui a été dit au sujet de comment trouver tous les nombres premiers,
À ce jour on sait pas le faire

non, on ne sait pas faire.
et ce serait la médaille Fields assurée.
alors bon courage....

[invite6486d7bd]

non, on ne sait pas faire.
et ce serait la médaille Fields assurée.
alors bon courage....

Moi je sais faire (en sciences ludiques bien sûr).
Allez-y, donnez-moi n'importe quel nombre, aussi grand que vous voulez, et je vous dis s'il est premier en quelques instants.

[invite51d17075]

je joue le jeu.
prenons les 500 chiffres de pi après la virgule.
je ne vais pas les lister.

ps : même si ce n'est pas le but de Iharmed qui les veux tous , et pas dire si l'un ou un autre l'est ou pas.

[invitedf3b174e]

Moi je sais faire (en sciences ludiques bien sûr).
Allez-y, donnez-moi n'importe quel nombre, aussi grand que vous voulez, et je vous dis s'il est premier en quelques instants.

bonjour
10^109 + 11^119 + 4

sachant que 10^109 + 11^119 + 3 est paire

[Deedee81]

Arf, bande de vicieux. Je m'attendais à tout sauf à ça. Je me demande ce que LeMulet a prévu

[invite51d17075]

un gros gag, certainement....
il avait prévenu du coté "ludique".

[invite51d17075]

bonjour
10^109 + 11^119 + 4

sachant que 10^109 + 11^119 + 3 est paire

divisible par 5, c'est quasi immédiat.

[Deedee81]

divisible par 5, c'est quasi immédiat.

Ah oui, tiens, bien vu ça