Forum INFOMATH
Vous souhaitez réagir à ce message ? Créez un compte en quelques clics ou connectez-vous pour continuer.
-34%
Le deal à ne pas rater :
-34% LG OLED55B3 – TV OLED 4K 55″ 2023 – 100Hz HDR 10+, ...
919 € 1399 €
Voir le deal

Recherche des nombres premiers palindromes

Aller en bas

07092008

Message 

Recherche des nombres premiers palindromes Empty Recherche des nombres premiers palindromes




Salut,

C'est une idée qui m'est venue à la tête ... je l'ai pas piquée d'un bouquin ni d'internet.

On va essayer de l'étudier de plus près ...

Un nombre T de longueur n est dit Palindrome s'il est symétrique :
T[1] = T[n],
T[2] = T[n-1],
...

de plus,

Un nombre premier est un entier naturel, admettant exactement deux diviseurs distincts dans Recherche des nombres premiers palindromes 624e4cf68723f677d53e8cf2272f348a (i.e : entiers et positifs) : 1 et lui-même.

On veut écrire un programme qui cherche les nombres Premiers et Palindromes s'ils existent bien sûr.

L'existence de tels nombres (à part le 11) n'est pas sure puisqu'on ne l'a pas démontrée mathématiquement (je vais essayer de le faire...) Si vous arrivez à démontrer que de tels nombres n'existent pas, alors, bravo!

Le meilleur programme serait :
- le plus rapide
- le plus optimal en mémoire
- le plus lisible et clair


Développer dans n'importe quel langage de programmation, et faites des captures d'écran, les coller dans ce topic... ne pas oublier de mentionner le temps d'exécution!

A VOUS DE JOUER...
methodiX
methodiX
Admin
Admin

Masculin
Nombre de messages : 1260
Localisation : Le couloir de l'école polytechnique de Tunis
Réputation : 68
Points : 7014
Date d'inscription : 22/03/2007

Feuille de personnage
Capacité linguistique:
Recherche des nombres premiers palindromes Left_bar_bleue1000/1000Recherche des nombres premiers palindromes Empty_bar_bleue  (1000/1000)

Revenir en haut Aller en bas

Partager cet article sur : reddit

Recherche des nombres premiers palindromes :: Commentaires

methodiX

Message Dim 7 Sep - 21:06 par methodiX

J'attends vos commentaires ...

Revenir en haut Aller en bas

informix

Message Lun 8 Sep - 19:25 par informix

Merci pour la proposition. J'ai fait un programme en Pascal. après je l'ai optimisé !!! il est bien ... je vais poser les statistiques après ... Smile


et vous les autres?

Revenir en haut Aller en bas

Napoléon

Message Mar 9 Sep - 12:25 par Napoléon

C'est très bien expliqué Methodix !!!

Il s'agit de faire un petit programme dans un langage donné, qui cherche ces nombres particuliers, s'ils existent biensûr.

Le meilleur programme sera celui le plus rapide, et clair et moins gourmand en ressources ...
(bienque ça soit un peu difficile de satisfaire toutes ces contraintes en même temps!)

Revenir en haut Aller en bas

Napoléon

Message Ven 12 Sep - 12:37 par Napoléon

Alors, c'est vrai que c'est pas trop compliqué comme travail demandé, mais, on peut toujours en faire un défi ... où est-ce que vous en êtes ?

Revenir en haut Aller en bas

lamia

Message Dim 14 Sep - 15:48 par lamia

Salut,
Je voulais vérifier une chose :

Si on a une liste de nombres premiers triée (dans un tableau T), et N un nombre à vérifier s’il est premier ou non,

On vérifie le reste de la division de N par chaque T[i], si c’est 0 donc c’est pas un nombre premier, sinon tant que la condition T[i]>√N, alors c’est un nombre premier.

Est-ce que ce raisonnement est correct (surtout en ce qui concerne la condition T[i]>√N) ?

Revenir en haut Aller en bas

avatar

Message Dim 14 Sep - 18:55 par edi9999

oui le raisonnement est correct

Revenir en haut Aller en bas

Napoléon

Message Lun 15 Sep - 11:24 par Napoléon

oui ce raisonnement est correct. Il possède déjà un nom que j'ai oublié Sad

NB: TantQue(T[i] <= SQRT(N)) et non pas >

Prends le cas de 25 pour vérifier...

Revenir en haut Aller en bas

Napoléon

Message Lun 15 Sep - 15:57 par Napoléon

jetez un coup d'oeil sur ce lien:

http://fr.wikipedia.org/wiki/Nombre_premier

Revenir en haut Aller en bas

avatar

Message Sam 20 Sep - 19:41 par manianis

Trouver les nombre premier palindromes ? c'est un bon sujet. Je vais m'y pencher.

Revenir en haut Aller en bas

Napoléon

Message Sam 20 Sep - 21:39 par Napoléon

oh manianis! bon retour monsieur ... ça fait longtemps que tu ne t'es pas connecté au forum.

Revenir en haut Aller en bas

Napoléon

Message Sam 20 Sep - 21:40 par Napoléon

J'attends ton défi Manianis Smile !

On verra cette fois-ci si tu ton programme va battre le mien ou non Very Happy

Revenir en haut Aller en bas

avatar

Message Jeu 25 Sep - 9:22 par manianis

Voici un snapshot d'une solution incomplete.

Code:
program pal_prem;

const pchif : array [1..4] of integer = (1, 3, 7, 9);

function est_premier(n : longint):boolean;
var
  bVal : boolean;
  bsup,
  nstart,
  ncount : longint;
begin
    if (n = 2) or
      (n = 3) or
      (n = 5) then bVal := True
    else if (n mod 2 = 0) or
            (n mod 3 = 0) or
            (n mod 5 = 0) then bVal := False
    else
        begin
            bsup := trunc(sqrt(n)) + 1;
            nstart := 7;
            bVal := True;

            while (bVal) and (nStart <= bSup) do begin
                  bVal := (n mod nStart <> 0);
                  nStart := nStart + 2;
                  while (nStart mod 3 = 0) or
                        (nStart mod 5 = 0) do nStart := nStart + 2;
            end;
        end;
    est_premier := bVal;
end;

procedure nombres_palindromes(n : longint ; var pl1, pl2 : longint);
var
    p, lm, lm1 : longint;
    r : integer;
begin
    p := 1;
    while (p <= n) do p := p * 10; p := p div 10;

    lm := p * p; lm1 := lm * 10;
    pl1 := n; pl2 := n;
    while (lm > p) do begin
        r := n mod 10;
        n := n div 10;
        pl1 := pl1 + r * lm;
        pl2 := pl2 + r * lm1;

        lm1 := lm;
        lm := lm div 10;
    end;
    pl2 := pl2 + (n mod 10) * lm1;
end;


var i, j, pl1, pl2 : longint;
begin
    for i:=0 to 20 do begin
        for j:=1 to 4 do begin
            nombres_palindromes(i*10+pchif[j], pl1, pl2);
            if (est_premier(pl1)) then Writeln(pl1:10);
            if (est_premier(pl2)) then Writeln(pl2:10);
        end;
    end;
end.

Revenir en haut Aller en bas

Napoléon

Message Jeu 25 Sep - 10:09 par Napoléon

manianis: bienque la solution est prometteuse, je vais la cacher quelques part parce que ce n'est pas un exercice, mais plutôt un Challenge. Donc il est plus motivant de présenter des statistiques de l'exécution du programme que de donner des éléments de réponse.

Par exemple, si tu nous mets un petit graphe (ou un tableau) décrivant le temps d'exécution de ton programme en fonction de n (le nombre en cours), tout le monde pourra avoir une idée sur la performance de ton programme, sans connaître comment tu l'as implémenté.

Amicalement.

Revenir en haut Aller en bas

Sami

Message Ven 26 Sep - 4:10 par Sami

nabiL a écrit:oui ce raisonnement est correct. Il possède déjà un nom que j'ai oublié Sad

NB: TantQue(T[i] <= SQRT(N)) et non pas >

Prends le cas de 25 pour vérifier...

ça s'appelle "crible d'eratosthène" Nabil

Revenir en haut Aller en bas

Napoléon

Message Ven 26 Sep - 12:41 par Napoléon

Sami a écrit:
nabiL a écrit:oui ce raisonnement est correct. Il possède déjà un nom que j'ai oublié Sad

NB: TantQue(T[i] <= SQRT(N)) et non pas >

Prends le cas de 25 pour vérifier...


ça s'appelle "crible d'eratosthène" Nabil


Merci Sami Wink

Revenir en haut Aller en bas

Message  par Contenu sponsorisé

Revenir en haut Aller en bas

Revenir en haut

- Sujets similaires

 
Permission de ce forum:
Vous ne pouvez pas répondre aux sujets dans ce forum