NOMBRE PREMIER SUIVANT

cs_Patrice99 Messages postés 1221 Date d'inscription jeudi 23 août 2001 Statut Membre Dernière intervention 9 septembre 2018 - 1 déc. 2006 à 13:15
cs_Patrice99 Messages postés 1221 Date d'inscription jeudi 23 août 2001 Statut Membre Dernière intervention 9 septembre 2018 - 4 déc. 2006 à 14:00

Cette discussion concerne un article du site. Pour la consulter dans son contexte d'origine, cliquez sur le lien ci-dessous.

https://codes-sources.commentcamarche.net/source/40533-nombre-premier-suivant

cs_Patrice99 Messages postés 1221 Date d'inscription jeudi 23 août 2001 Statut Membre Dernière intervention 9 septembre 2018
4 déc. 2006 à 14:00

Exact, VB6 est plus rapide que VB2005 de 25% si on reste en Double, et le type Double reste pratiquement 2x plus rapide que le type Long de VB2005, alors que j'ai pourtant optimisé avec \ (sinon c'est carrément très lent).

cs_DarkVader Messages postés 51 Date d'inscription samedi 21 octobre 2000 Statut Membre Dernière intervention 10 octobre 2011
4 déc. 2006 à 12:04

Sorry,
pour les grands nombres

estPair ((n / 2) Int(n / 2))
c = n + 1 + Abs(estPair + 1)

cs_DarkVader Messages postés 51 Date d'inscription samedi 21 octobre 2000 Statut Membre Dernière intervention 10 octobre 2011
4 déc. 2006 à 11:56

Bravo pour la base mathématique de l'algo -

(Pour ce genre d'opération, .net est bien moins rapide que vb6)

Une petite optimisation toute bête permettant de diviser par 2 le temps de calcul :

Function PreSuiv(n As Double) As Double
Dim c As Double, d As Double, f As Double, i As Double, j As Double, t As Double
Dim temps

c n + 1 + Abs(n Mod 2 1)
d = Int(n + Sqr(n) + 9)

f = 1
For i = c To d Step 2
t = 0
For j = 1 To Int(Sqr(i))
t = t + Int(i / j) - Int((i - 1) / j)
Next j
t = 2 - (2 * t)
f = f * (-Int(t / i))
If t = f Then Exit For
'If t = 0 Then Exit For
Next

PreSuiv = i
End Function

us_30 Messages postés 2065 Date d'inscription lundi 11 avril 2005 Statut Membre Dernière intervention 14 mars 2016 10
3 déc. 2006 à 17:12

Oui tu as probablement raison, mais je m'attache plus à l'algorithme. De plus, je tiens à préciser qu'on peut aller vraiment plus vite (sans comparaison) avec mon autre code NPD... mais le principe est très différent de celui-ci, bien sur.

Amicalement,
Us.

cs_Patrice99 Messages postés 1221 Date d'inscription jeudi 23 août 2001 Statut Membre Dernière intervention 9 septembre 2018
3 déc. 2006 à 11:38

Tu devrais essayer avec VB 2005 (qui est gratuit), la capacité du long a doublée en nombre de bits : à mon avis, je ne crois pas que le double apportera quelque chose en plus avec une telle capacité, et les traitements devrais être vraiment plus rapides avec des Long de VB8.
Int64 VB8.Long : MaxValue 9223372036854775807

us_30 Messages postés 2065 Date d'inscription lundi 11 avril 2005 Statut Membre Dernière intervention 14 mars 2016 10
2 déc. 2006 à 23:07

Bonsoir,

Pour répondre aux questions? i\j est identique à Int(i/j), sauf que la première forme n'est pas utilisable au-delà de la limite d'un Long, quel que soit le type déclaré?

Exemple :

Sub essai()
Dim A As Double, B As Double, C As Double, D As Double
A = 2147483647
B = A + 1
C = A \ 2
Debug.Print C
D = B \ 2
Debug.Print D
End Sub

2147483647 est la limite du type long.

Le code cause une erreur sur D? Il faudrait s'arrêter au type Long pour utiliser « \ »? et dans ce cas, le programme serait optimale en vitesse, mais pas dans la plage de valeurs? c'est un choix.

Ensuite on peut choisir pour N, le type Currency? mais avec le type Double on peut aller plus loin? et plus vite.

Exemple :
Sub essai()
Dim A As Currency, B As Double
A = 922337203685477#
B = CDbl(A) + 10000000000000#
Debug.Print A, B
End Sub

922337203685477 est la limite de Currency, qu'alors avec B on peut aller au-delà? tout en restant en format d'un nombre entier?

Mettre dans une variable Q pour la limite de la boucle FOR permet un très très léger gain de temps, d'après mes tests. A peine 1 seconde sur 89 secondes? mais bon, c'est déjà ça. De plus, on peut retirer les parenthèses inutiles des deux lignes :
T = 2 - 2 * T
F = -F * Int(T / I)

Ensuite, d'un point mathématique, j'ignore la raison pour laquelle on a D = Int(N + Sqr(N) + 9)? voir le site, si quelqu'un trouve pourquoi?

Il est possible que ce code soit encore optimisable? même s'il est déjà très performant?

Rq : Il est à noter que ce code, peut très bien s'adapter pour savoir si un nombre est premier ou pas. Il suffit pour cela de tester si N-1=N.

Amicalement,
Us.

cs_comme Messages postés 122 Date d'inscription dimanche 19 mars 2006 Statut Membre Dernière intervention 18 juillet 2009
1 déc. 2006 à 19:30

Tres bon travail , du point de vue mathématiques je veux savoir pourqoi l'expression intermediaire: D = Int(N + Sqr(N) + 9) audebut

cs_Patrice99 Messages postés 1221 Date d'inscription jeudi 23 août 2001 Statut Membre Dernière intervention 9 septembre 2018
1 déc. 2006 à 14:03

2) : je crois que la fin de la boucle n'est évaluée qu'une fois, donc pas de gain ici.

violent_ken Messages postés 1812 Date d'inscription mardi 31 mai 2005 Statut Membre Dernière intervention 26 octobre 2010 2
1 déc. 2006 à 13:47

Salut, deux petites questions sur l'optimisation du code :

1) pourquoi utiliser le type Double ? Si c'est pour de grands nombres, autant prendre Currency, ou alors limiter au Long pour plus de vitesse.

2) Il me semble (jmais e peux me tromper) que "For J 1 To Int(Sqr(I))" est moins rapide que "For J 1 To Q" (avec Q=Int(Sqr(I))).

@+

cs_Patrice99 Messages postés 1221 Date d'inscription jeudi 23 août 2001 Statut Membre Dernière intervention 9 septembre 2018
1 déc. 2006 à 13:15

Pour aller plus vite : i \ j = Int(i / j)

Discussions similaires

Calcul du n-ième nombre premier

Nombre Premier

génerateur de nombre aléatoire

Nombre de semaines dans l'année

decomposition d'un nombre en java

Votre réponse

Discussions similaires