Salut,
j'essaye de coder un algo pour trouver tous les nombres premiers dans un intervalle.

La technique me semble à priori simple :

On regarde si le nombre est divisible par 2, 3, 4, 5, 6, 7, 8, 9.
Si il divisible uniquement par un ou lui même, il est premier.

Cela marche pour des petits nombres.
Mais seulement, prenons le cas de 169.
169 n'est pas premier, pourtant il n'est divisible par aucun des chiffres de 2 à 9.

J'en suis venu à l'idée, que si sa racine était ronde, bah il n'était pas premier (c'est le cas de 169, sqrt(169) = 13).

Que pensez-vous de cette idée ?
Reste t'il des cas que je n'aurais pas imaginé ?


Ensuite, comment vérifier que cette racine est ronde ?
Je ne veux pas utiliser de fonction connexe, car je pense que pour comprendre les bases, faut comprendre en détails, et reprendre le même chemin que certains.
Pas trop d'idée pour l'instant, c'est pour ça que j'implore votre aide.
Cette solution est donc plus mathématique que "C", mais c'est pas grave.

Merci

++

En fait un nombre entier supérieur à 1 est premier si il n'est divisible que par 1 et lui même.
Donc en fait tu testes si le nombre est divisible par tout les nombres entre lui même exclu et sa racine carrée inclue (oui car après la racine carrée les divisions reviennent dans l'autre sens, je me comprend en tout cas).
Donc il ne faut pas se limiter aux nombres de 1 à 9.

Sinon pour d'autres algos : Google .

Duarna

+1

Une petite boucle devrait tout arranger

non testé:



Je doute que ça marche! En plus, je suis fatiguée !!!

Il faut que par exemple pour 147 tu cherches la racine et que tu test tous les diviseurs jusqu'à cette racine. Tu peux exclure les nombres pairs et il faut aussi que ton programme s'arrête dès qu'il a trouvé 1 diviseurs ( a part 1 et 147 ).

[EDIT] Grillé je m'en doutais

tu testes la division non pas par "tous les nombres", mais seulement par "les nombres premiers inférieurs à sqrt(N)"
(1er test : si N%2==0 => pas premier)

Voila l'algo en pseudo code

dark-lod, 10/5 = 2 donc 10 n'est pas premier. Selon ton algo, si 10/5 = 0 alors 10 n'est pas premier....

Voir mon edit plus haut

Rien dit, pas con!

d'ailleurs, je vais éditer mon code plus haut avec ta méthode!

Bravo (j'ai honte .... )

je vien de modifier le pseudo code je crois qu'il correspond à celui de mon livre de spé maths

Il vaut mieux utiliser un crible d'Erathostène.
Bien plus rapide.

Citation : minirop

tu testes la division non pas par "tous les nombres", mais seulement par "les nombres premiers inférieurs à sqrt(N)"
(1er test : si N%2==0 => pas premier)

Oui mais justement on cherche les nombres premiers donc pour tester avec les nombres premiers il faut les connaitre.

Sauf qu'un nombre a une décomposition en produits de facteurs premiers, et que cette décomposition est unique

Les maths ça aide, vous étiez prévenus

Citation : Honor

Citation : minirop

tu testes la division non pas par "tous les nombres", mais seulement par "les nombres premiers inférieurs à sqrt(N)"
(1er test : si N%2==0 => pas premier)

Oui mais justement on cherche les nombres premiers donc pour tester avec les nombres premiers il faut les connaitre.

Et si tu les stockes au fur et à mesure que tu les trouves?

Je répète que le crible d'Erathostène est bien plus efficace.

Citation : Pole

Citation : Honor

Citation : minirop

tu testes la division non pas par "tous les nombres", mais seulement par "les nombres premiers inférieurs à sqrt(N)"
(1er test : si N%2==0 => pas premier)

Oui mais justement on cherche les nombres premiers donc pour tester avec les nombres premiers il faut les connaitre.

Et si tu les stockes au fur et à mesure que tu les trouves?

Je répète que le crible d'Erathostène est bien plus efficace.

Merci beaucoup pour cette technique, qui apparemment est très efficace (on a pu trouver des nombres premiers énormes grâce à ça).
En plus, relativement simple, merci


Mais au passage, si j'ai un double :

double bla = 12.899;
Comment faire pour le faire passer à 12 sans cast, donc sans utiliser une fonction (en gros je veux coder cette fonction de troncature, mais je sais pas trop comment m'y prendre). Auriez vous une piste ?

Merci pour votre aide

pourquoi sans cast ?

J'avais réalisé un algorithme dans le genre l'année dernière lorsque je commençais à apprendre la programmation (c'était en JAVA, mais l'algo est le même).

L'idée toute simple est de stocker les nombres premiers dans un tableau.
Tu fais un tableau pouvant accueillir le maximum de case (pour aller loin dans les nombres premiers).

La première case contient le nombre 2.

Ensuite, pour chaque nombre de 0 à l'infini (ou autre). Tu tente de le diviser par tous les nombres premiers le précédant et étant supérieur à sa racine carrée. Si le modulo est toujours différent de 0, alors tu le stocke dans ton tableau...

Bah parce que j'ai pas envie d'utiliser de cast, j'essaye de comprendre comment faire sans

Tu veux tronquer ou arrondir????

Pour arrondir tu as:



PS: je viens de me rendre compte que pour tronquer, un nombre, tout ce qu'on fait c'est l'arrondir à l'inférieur donc floor marcherait

Citation : kouaygon

Tu veux tronquer ou arrondir????

Pour arrondir tu as:

ceil(variable);//Pour arrondir au supérieur
floor(variable);//Pour arrondir à l'inférieur
round(variable);//Pour arrondir un DECIMAL(double)
//......Il y en a d'autres +/- utiles

PS: je viens de me rendre compte que pour tronquer, un nombre, tout ce qu'on fait c'est l'arrondir à l'inférieur donc floor marcherait

Ouais, donc je veux coder la fonction de troncature, sans utiliser d'autres fonctions.
C'est juste pour comprendre comment ça marche, car j'aurais bien d'autres programmes plus utiles à faire
Donc j'aurais juste besoin d'un coup de pouce.

Essaye de mettre ton double dans un int

tu fais une boucle qui tourne jusqu'à ce que i soit plus grand que ton nombre n

alors, tu prends i-1 et c'est ton nombre tronqué

c'est peut etre pas le plus rapide, mais au moins ca marche ...

Ui mais ma solution marche aussi et en plus elle est plus rapide

ha, ui, j'avais pas vu que je m'étai fait griller

en effet, ca marche très bien

Impec, merci

hi please je veux une fonction qui donne tous le nombre premier avant un nombre donne example 10 :2,3,5,7;

Et bien moi je veux un poney. On va être déçus tous les deux...

Bonjour!!!

Je réponds au nom de KYALONDAWA KAZAMWALI Asaph suis un ingénieur de l'université de KINSHASA du Département de Mathématiques Informatique, je suis très ravis d'avoir lu la réflexion de nos plusieurs collègues concernant l'algorithme d'un nombre premier mais je voulais juste proposé un algo que j'ai implémenté en Visuel Basic.Net en mode console qui réponds à toutes vos préoccupations concernant "UN NOMBRE PREMIER" Merci. Et si vous d'autres préoccupation suis à votre service.

Module Module1

    Sub Main()
        Dim n, asaph, i, j As Integer
        Console.Out.WriteLine("veillez saisie la nième nombre SVP:")
        n = CInt(Console.In.ReadLine())
        Console.Out.WriteLine("Les nombres parfaits qui existent entre 1 et " & n.ToString & " sont:")
        Console.Out.WriteLine("1")
        For i = 2 To n
            asaph = 0

            For j = 2 To (i ^ (1 / 2))
                If (i Mod j) = 0 Then
                    asaph = asaph + 1
                End If
            Next
            If asaph = 0 Then
                Console.Out.WriteLine(i.ToString)
            End If
        Next
        Console.In.ReadLine()
    End Sub

End Module

**********Algorithme NOMBRE-PREMIER***********

#include <stdio.h>

void main()
{ int A,I,R;
  int Premier;


printf("Saisir un nombre entier positif \n");
scanf("%d",&A);


  if (A==1)

 { printf("Votre nombre n'est pas premier \n");
 }

 else
  {
   if((A==2) && (A==3))
     printf("votre nombre est premier \n");
    }
  for(I=1;I<=A/2;I++)
   {
   R=A%I;
I=A/2;
   if ((R==0)&&(I!=2))

      Premier=0;
   else
    {Premier=1;}

   if (Premier=0)
     printf("Votre nombre n'est pas premier \n");
    else { printf("Votre nombre est premier");
   }

  }

    }

MERCI DE LIRE LES REGLES DU FORUM

Il y a un bouton (</>) pour poster le code, la c'est illisible!!

-
Edité par zzzflo 20 novembre 2015 à 11:19:33

Je ne suis pas informaticien et encore moins mathématicien, cependant je suis bon observateur , ou disons j'ai assez observé les nombres premiers ,des mathématiciens souvent les vois comme un chaos ,du moins c'est ce que m'a appris internet , mais moi,j'a dépassé le crible d’Ératosthène , je ne suis même pas obligé de connaitre les nombres premiers pour tester si un nombre est premier ,seulement je m'aide parfois d'Excel , dix minute parfois me suffisent pour dénicher un nombre premier de la taille de 9999999999999999997 ; pour ceux qui connaissent comment produire un algorithme,cette méthode révolutionnera les tests de primalité