Rechercher : dans
Par :

Algo nombres premiers

Dernière réponse le 14 oct 2009 à 13:34:23 jeje_42, le 17 fév 2009 à 15:59:22 
 Signaler ce message aux modérateurs

Bonjour,

Je voudrais créer un algo très simple qui permet de savoir si un nombre est premier ou pas, en calculant le reste de ses divisions successives par tous les nombres qui le précèdent.

Mon script:


#!/bin/bash

ARGS=1

i=2

while [ $(($1%i)) -ne 0 ]
do
i='expr i+1'
done

if [ i -ne $1 ]; then
echo " $1 n'est pas premier ! voici deux diviseurs :"
echo i
echo $(($1/i))
else
echo " $1 est premier !"
fi


Malheureusement, j'ai deux erreurs lorsque je lance par exemple

./script.sh 51

Voici mon output :

./script.sh: line 7: expr i+1: expression recursion level exceeded (error token is "i+1")
./script.sh: line 9: [: i: integer expression expected
51 est premier !

Merci d'avance à tous ceux qui essaieront de m'aider !

Jerome

Configuration: Linux Red Hat

Meilleures réponses pour « Algo nombres premiers » dans :
Vérifier si un nombre entier est un nombre premier en C Voir Définition nombre premier Algorithme 1 : les diviseurs compris entre 2 et N-1 seront testés Algorithme 2 : les diviseurs pairs ne seront pas testés, la recherche se limitant aux diviseurs impairs Algorithme 3 : les diviseurs impairs jusqu'à la...
Exercice assembleur x86 nombre premier VoirIntroduction Notions abordées dans cet exercice Enoncé Rappel Corrigé Explication Introduction Ce petit exercice d'assembleur vise les architectures x86 (Processeurs Intel et Amd 32 bits) et utilise la syntaxe de Nasm, un assembleur...
[PHP] Dernier jour du mois / Nombre de jours dans le mois VoirSoient $m le numéro du mois en question et $y l'année. La fonction date() permet d'afficher directement le nombre de jours dans le mois avec le caractère "t" :
J'ai un ordinateur pour la première fois, je ne connais rien VoirVoici un article qui pourra bien vous aider si c'est la première fois que vous utilisez un ordinateur. Les principaux composants d'un ordinateur y sont détaillés, ainsi que le vocabulaire (jargon informatique de base) qui s'y rapporte. Note d'un...
Télécharger Adobe Premiere Pro VoirAdobe Premiere est un programme de renom dans le montage et l'édition de vidéos. Il comprend plusieurs outils pratiques et des fonctionnalités complètes. Il permet entre autre d'éditer vidéo et audio avec une multitude d'options. Adobe Premiere...
Représentation des nombres entiers et réels VoirReprésentation d'un nombre dans un ordinateur On appelle représentation (ou codification) d'un nombre la façon selon laquelle il est décrit sous forme binaire. La représentation des nombres sur un ordinateur est indispensable pour que celui-ci...
Système hexadécimal VoirSystème hexadécimal Les nombres binaires étant de plus en plus longs, il a fallu introduire une nouvelle base : la base hexadécimale. La base hexadécimale consiste à compter sur une base 16, c'est pourquoi au-delà des 10 premiers chiffres on a...
Servlets - Première Servlet VoirPremiere servlet Voici un exemple simple de servlet dont le seul but est d'afficher du texte sur le navigateur du client : import javax.servlet.*; import javax.servlet.http.*; import java.io.*; public class PremiereServlet extends HttpServlet { ...

1

LennyPourVoir, le 17 fév 2009 à 18:10:27

#!/bin/bash

i=2

while [ $(($1%i)) -ne 0 ]
do
i=$((i+1))
echo $i
done

if [ $i -ne $1 ]; then
echo " $1 n'est pas premier ! voici deux diviseurs :"
echo $i
echo $(($1/i))
else
echo " $1 est premier !"
fi


Voilà qui devrait mieux marcher, par ailleurs ton algo n'est pas du tout optimisé.
Si le nombre n'est pas divisible par 2 on peut ajouter 2 à i ...
De plus dès que le quotient dépasse le diviseur on peut s'arrêter ....
Pour 51 inutile l'aller jusqu'à 51, jusqu'à 7 suffit ! (7*7=49, 8*8=64)

Répondre à LennyPourVoir

2

 TiboleParano, le 14 oct 2009 à 13:34:23

Oui, comme dit LennyPourVoir, pour un algorithme de nombres premiers tu divise le nombre par les entiers jusqu'à sa racine carrée: s'il n'y a pas de solution [=0] avant, il n'y en aura pas d'autres après, et le nombre est premier
ensuite, pour optimiser l'algo, vu qu'au bout d'un certain nombre de nombres (haha) il doit bien ramer, on peut srappeller le théoreme de mon prof de terminale, celui qui explique pourquoi il existe une infinité de nombre premier:
si P[0] est le premier nombre premier (2); P[1] le 2e (3) ... et P[n] le dernier trouvé dans ta liste, alors P[1]*P[2]*...*P[n] n'est pas premier, vu qu'il peut être divisé par les nombres premiers précédents, mais (P[1]*P[2]*...*P[n]) +1 l'est :)

Répondre à TiboleParano