Les nombres premiers version super algo

Soyez le premier à donner votre avis sur cette source.

Vue 4 874 fois - Téléchargée 261 fois

Description

Salut a tous !

Voilà encore un programme qui traîte des nombres premiers !!! Si je poste cette source, c'est parce que je n'ai trouvé aucune source sur ce site qui soit aussi rapide que celle-ci !
En effet la plupart traite les nombres premiers selon leurs propriétés ( divisibilité, décomposition en facteur... ) alors que cette source est la simple transposition du crible d'Eratosthène. Et comme il est beaucoup plus rapide de faire des additions que des divisions, le résultat ( en temps ) est assez impressionant pour seulement 10 lignes de code.

Hélas la source originale n'est pas de moi, c'est juste la transcription d'un programme trouvé dans un livre d'exos de C++ ( c'était la feinte ! ). Le principal c'est l'algo ! Dailleurs j'ai mis celui en C pour ceux que ca interresse ( 8 lignes ).
Soyez quand même indulgent, c'est un de mes premiers prog, il sort du placard !

@++

Source / Exemple :


'Algorithme
    'Incrémente prem jusqu'a la racine carré du nombre max
    Do While prem * prem < Text1
    
    'Premier multiple de prem
    i = 2 * prem
        
    'Tous les multiples de prem seront mis en true
        Do
            Tableau(i) = True
            i = i + prem
        Loop Until i > Text1
        
    'Va jusqu'au nombre premier suivant, le false suivant
        Do
            prem = prem + 1
        Loop Until Tableau(prem) = False
                
    Loop

Conclusion :


Compilé sur un P4 2.4Ghz avec 256 DDR : à peu près 11s pour les nombres premiers < 1 000 000
pour l'info il y en à 78 498
Le plus long, c'est l'affichage > 1 m

Il est à noter une différence de 3 secs entre le programme compilé et interprêté par VB, pour des additions ca fait pas mal !

ATTENTION : le tableau est limité, faut pas exagérer quand même !

Codes Sources

A voir également

Ajouter un commentaire

Commentaires

cs_neria
Messages postés
320
Date d'inscription
vendredi 21 février 2003
Statut
Membre
Dernière intervention
16 février 2009
-
merci beaucoup :)
ticomic
Messages postés
57
Date d'inscription
mercredi 22 décembre 2004
Statut
Membre
Dernière intervention
29 avril 2005
-
Bravo!
C'est très simple, rapide et fonctionnel.

10/10
cs_neria
Messages postés
320
Date d'inscription
vendredi 21 février 2003
Statut
Membre
Dernière intervention
16 février 2009
-
Salut Saros !

Merci pour le 10 ! Pour répondre à ta question, ce n'est malheureusement pas l'algorithme des trois Indiens que j'ai implémenté, mais la simple application du crible d'Eratosthène. Mais si j'ai le temps je vais essayer de me pencher sur cet algo.
Hélàs je n'ai plus l'adresse internet de leur site, mais j'ai quand même la doc. Un petit mail à : neria@libertysurf.fr
et je te l'envoie !

@+


PS : tu peut peut être trouver l'adresse du site sur le site de science et vie
Saros
Messages postés
921
Date d'inscription
vendredi 20 décembre 2002
Statut
Membre
Dernière intervention
23 septembre 2010
-
J'aimerais bien en effet avoir la doc, si c'est possible que tu me donnes l'adresse.....
En tout cas ton programme est parfaitement fonctionnel, bravo...
10/10
Une question : c'est l'algorithme des 3 indiens dont tu parles (qui est paru dans un Science et Vie il me semble) que tu as implémenté ?
Saros
cs_neria
Messages postés
320
Date d'inscription
vendredi 21 février 2003
Statut
Membre
Dernière intervention
16 février 2009
-
Salut !

Oui, je sais, tu parles entres autres de l'algo des 3 indiens : 13 lignes de fortran pour savoir si un nombres est premier ou pas ! J'ai l'algo et la doc, si ca interresse quelqu'un ( format PDF : 9 pages 208 Ko ). Personnellement je n'ai rien compris, c'est assez balaise ( niv BAC+beaucoup ) et en plus c'est en anglais.
Remarque, même si l'algo de ma source est contraignant, c'est quand même le plus rapide de VBFrance pour seulement 10 lignes !

Vous n'êtes pas encore membre ?

inscrivez-vous, c'est gratuit et ça prend moins d'une minute !

Les membres obtiennent plus de réponses que les utilisateurs anonymes.

Le fait d'être membre vous permet d'avoir un suivi détaillé de vos demandes et codes sources.

Le fait d'être membre vous permet d'avoir des options supplémentaires.