π
<-
Chat plein-écran
[^]

Déterminer le nième nombre premier.

:32tins: :32tinsktpb: :32tinsktpn: :32tinscas: :32tinstpkc: :32tinstpktpb: :32tinstp: :32tinscastp: :32tinscmc: :32tinscx: :32tinscxcas:

Re: Déterminer le nième nombre premier.

Unread postby parisse » 07 Mar 2021, 20:38

Il n'y a pas lieu de calculer un n2 ici.
Il vaut mieux a mon avis tester la parite en premier et utiliser une boucle for qu'une boucle while dans un cas comme celui-ci, ca evite d'oublier d'incrementer la variable d'indice, donc en Python mettre for k in range(3,n,2): puis utiliser un test et un return: if k*k>n: return 1
En C, tout se fait dans l'instruction for.
Code: Select all
// pour n<2^32
if (n<2) return 0;
if (n%2==0) return n==2;
for (unsigned k=3;k*k<=n;k+=2){
  if (n%k==0) return 0;
}
return 1;

L'astuce d'ajouter 2*k+1 a une variable pour tester ne sert pas reellement ici, car on ne va pas tester de tres grandes valeurs de k, ca prendrait trop de temps, disons pas plus que 2^16 en pratique, donc k*k va se faire en multipliant des entiers 32 bits, ce qui prend 1 cycle sur les CPU modernes.
Ce qui prend le plus de temps, c'est le calcul du reste euclidien.
Et si on veut optimiser encore plus, on utilise une table de nombres premiers, par exemple <=10000 pour eviter de tester avec des entiers non premiers.
User avatar
parisseVIP++
Niveau 12: CP (Calculatrice sur Pattes)
Niveau 12: CP (Calculatrice sur Pattes)
Level up: 17.5%
 
Posts: 2338
Joined: 13 Dec 2013, 16:35
Gender: Not specified

Re: Déterminer le nième nombre premier.

Unread postby Bisam » 10 Mar 2021, 20:38

Mais tu as parfaitement raison : j'ai fait n'importe quoi... Je n'avais pas les yeux en face des trous.

Je corrige dans les messages précédents.
User avatar
BisamAdmin
Niveau 15: CC (Chevalier des Calculatrices)
Niveau 15: CC (Chevalier des Calculatrices)
Level up: 52.2%
 
Posts: 5563
Joined: 11 Mar 2008, 00:00
Location: Lyon
Gender: Male
Calculator(s):

Previous

Return to Problèmes divers / Aide débutants

Who is online

Users browsing this forum: No registered users and 12 guests

-
Search
-
Social
-
Featured topics
Comparaisons des meilleurs prix pour acheter sa calculatrice !
Découvre les nouvelles fonctionnalités en Python de l'OS 5.2 pour les Nspire CX II
Découvre les nouvelles fonctionnalités en Python de l'OS 5.5 pour la 83PCE/84+C-T Python Edition
Omega, le fork étendant les capacités de ta NumWorks, même en mode examen !
1234
-
Donations / Premium
For more contests, prizes, reviews, helping us pay the server and domains...
Donate
Discover the the advantages of a donor account !
JoinRejoignez the donors and/or premium!les donateurs et/ou premium !


Partner and ad
Notre partenaire Jarrety Calculatrices à acheter chez Calcuso
-
Stats.
495 utilisateurs:
>476 invités
>13 membres
>6 robots
Record simultané (sur 6 mois):
6892 utilisateurs (le 07/06/2017)

-
Other interesting websites
Texas Instruments Education
Global | France
 (English / Français)
Banque de programmes TI
ticalc.org
 (English)
La communauté TI-82
tout82.free.fr
 (Français)