Impression des nombres premiers de 1 à 100

Ce code c++ imprime la suite des nombres premiers: 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97.

Mais je ne pense pas que c'est la façon dont mon livre veut qu'il soit écrit. Il mentionne quelque chose à propos de la racine carrée d'un nombre. J'ai donc essayé de changer mon 2ème boucle à for (int j=2; j<sqrt(i); j++) mais il ne me donne pas le résultat que j'ai besoin.

Comment aurais-je besoin de modifier ce code à la façon dont mon livre veut qu'il soit?

int main () 
{
    for (int i=2; i<100; i++) 
        for (int j=2; j<i; j++)
        {
            if (i % j == 0) 
                break;
            else if (i == j+1)
                cout << i << " ";

        }   
    return 0;
}

Un entier premier numéro est celui qui a
exactement deux diviseurs,
à savoir 1 et le nombre lui-même. Écrire,
exécuter et tester un programme en C++ qui
découvre et imprime tous les nombres premiers
moins de 100. (Indice: 1 est un nombre premier
numéro. Pour chaque nombre de 2 à 100,
trouver Reste = Nombre % n, où n
varie de 2 à sqrt(nombre). \ N
est plus grand que sqrt(nombre), la
le nombre n'est pas divisible par n.
Pourquoi? Si le Reste est égal à 0, le
le nombre n'est pas un nombre premier.)

source d'informationauteur Sahat Yalkabov

algorithm c c++primes

Trois façons:

int main () 
{
    for (int i=2; i<100; i++) 
        for (int j=2; j*j<=i; j++)
        {
            if (i % j == 0) 
                break;
            else if (j+1 > sqrt(i)) {
                cout << i << " ";

            }

        }   

    return 0;
}

int main () 
{
    for (int i=2; i<100; i++) 
    {
        bool prime=true;
        for (int j=2; j*j<=i; j++)
        {
            if (i % j == 0) 
            {
                prime=false;
                break;    
            }
        }   
        if(prime) cout << i << " ";
    }
    return 0;
}

#include <vector>
int main()
{
    std::vector<int> primes;
    primes.push_back(2);
    for(int i=3; i < 100; i++)
    {
        bool prime=true;
        for(int j=0;j<primes.size() && primes[j]*primes[j] <= i;j++)
        {
            if(i % primes[j] == 0)
            {
                prime=false;
                break;
            }
        }
        if(prime) 
        {
            primes.push_back(i);
            cout << i << " ";
        }
    }

    return 0;
}

Edit: Dans le troisième exemple, nous gardons la trace de l'ensemble de nos précédemment calculé les nombres premiers. Si un nombre est divisible par un nombre premier, il est également le premier <= diviseur qui il est également divisble par. Cela réduit le calcul par un facteur de primes_in_range/total_range.

14

Si j est l'égalité des à sqrt(i) il pourrait également être un facteur, non seulement si elle est petits.

Pour itérer jusqu'à et y compris sqrt(i) dans votre boucle, vous pourriez écrire:
```
for (int j=2; j*j<=i; j++)
```
(Par rapport à l'utilisation sqrt(j) cela a l'avantage de ne pas besoin de la conversion de nombres en virgule flottante.)
10

Si un numéro a diviseurs, au moins l'un d'entre eux doit être inférieur ou égal à la racine carrée de ce nombre. Lorsque vous vérifiez les diviseurs, vous avez uniquement besoin de vérifier pour la racine carrée, pas tout le chemin jusqu'à le nombre en cours d'essai.

C'est ma très simple programme en c++ à la liste des nombres premiers entre 2 et 100.

for(int j=2;j<=100;++j)
{
    int i=2;
    for(;i<=j-1;i++)
    {
        if(j%i == 0)
            break;
    }

    if(i==j && i != 2)
        cout<<j<<endl;
}

4

effectivement la meilleure solution est d'utiliser "Un premier tamis ou du premier numéro de tamis" qui "est un fast-type d'algorithme pour trouver les nombres premiers" .. wikipedia

La simple (mais pas la plus rapide) algorithme est appelé "crible d'eratosthène" et peut être fait dans les étapes suivantes(à partir de wikipédia nouveau):
1. Créer une liste de nombres entiers consécutifs à partir de 2 à n: (2, 3, 4, ..., n).
2. D'abord, permettez-p égal à 2, le premier nombre premier.
3. À partir de p, comptez en incréments de p et marquer chacun de ces nombres plus grand que p lui-même dans la liste. Ces numéros seront
  2p, 3p, 4p, etc.; notez que certains d'entre eux ont déjà été marqués.
4. Trouver le premier nombre plus grand que p dans la liste qui n'est pas marqué. Si il n'y avait pas de numéro, arrêter. Sinon, laissez p est égal
  ce nombre (qui est le prochain premier), et recommencez à partir de l'étape 3.
3

À l'aide de Crible d'Eratosthène logique, je suis en mesure d'obtenir les mêmes résultats avec beaucoup plus rapide vitesse.

Mon code de démo VS accepté de répondre à.

Comparant les count
mon code prend de manière significative moins d'itération pour terminer le travail. Checkout les résultats pour les différents N valeurs à la fin.

Pourquoi ce code fonctionne mieux que d'ores et déjà acceptées:

- même les chiffres ne sont pas contrôlés, même une fois tout au long du processus.

- deux boucles internes et externes sont de vérifier que dans la limite du possible. Pas de superflu et de contrôles.

Code:
```
int N = 1000; //Print primes number from 1 to N
vector<bool> primes(N, true);
for(int i = 3; i*i < N; i += 2){    //Jump of 2
    for(int j = 3; j*i < N; j+=2){  //Again, jump of 2
        primes[j*i] = false;
    }
}
if(N >= 2) cout << "2 ";
for(int i = 3; i < N; i+=2){        //Again, jump of 2
    if(primes[i] == true) cout << i << " "; 
}
```
Pour N = 1000mon code prend 1166 itérations, a accepté de répondre prend 5287 (4,5 fois plus lent)

Pour N = 10000mon code prend 14637 itérations, a accepté de répondre prend 117526 (8 fois plus lent)

Pour N = 100000mon code prend 175491 itérations, a accepté de répondre prend 2745693 (15.6 fois plus lent)

Trouver les nombres premiers inférieurs à un 100 est particulièrement agréable et facile:

    printf("2 3 ");                        //first two primes are 2 and 3
    int m5 = 25, m7 = 49, i = 5, d = 4;
    for( ; i < 25; i += (d=6-d) )
    {
        printf("%d ", i);                  //all 6-coprimes below 5*5 are prime
    }
    for( ; i < 49; i += (d=6-d) )
    {
        if( i != m5) printf("%d ", i);
        if( m5 <= i ) m5 += 10;            //no multiples of 5 below 7*7 allowed!
    }
    for( ; i < 100; i += (d=6-d) )         //from 49 to 100,
    {
        if( i != m5 && i != m7) printf("%d ", i);
        if( m5 <= i ) m5 += 10;            //  sieve by multiples of 5,
        if( m7 <= i ) m7 += 14;            //                      and 7, too
    }

La racine carrée de 100 est 10et si cette version de le crible d'Eratosthène avec le 2-3 roue utilise les multiples de juste les premiers ci-dessus 3 qui ne sont pas plus grand que 10 -- à savoir. 5 et 7 seul! -- pour tamiser la 6-sont premiers entre eux ci-dessous 100 manière progressive.

2

C'est bien de changer votre boucle for pour for (int j=2; j<=sqrt(i); j++) mais alors vous aussi besoin de changer quelque chose d'autre. À la recherche spécifiquement à votre impression condition,
```
else if (i == j+1) {
      cout << i << " ";
}
```
pourquoi que jamais être déclenchée si vous ne itérer jusqu'à sqrt(i)? Où pouvez-vous déplacer le cout pour changer cela? (Astuce: vous pouvez déplacer l'impression de sortir de la boucle, puis faire usage d'un certain type de variable d'indicateur)

- Je vérifier si un nombre est premier ou pas avec le code suivant( bien sûr, utiliser sqrt ):

bool IsPrime(const unsigned int x)
{
  const unsigned int TOP
  = static_cast<int>(
      std::sqrt( static_cast<double>( x ) )
    ) + 1;

  for ( int i=2; i != TOP; ++i )
  {
    if (x % i == 0) return false;
  }
  return true;
}

- Je utiliser cette méthode pour déterminer les nombres premiers:

#include <iostream>
using std::cout;
using std::cin;
using std::endl;
#include <cmath>
void initialize( unsigned int *, const unsigned int );
void show_list( const unsigned int *, const unsigned int );
void criba( unsigned int *, const unsigned int );
void setItem ( unsigned int *, const unsigned int, const unsigned int );
bool IsPrime(const unsigned int x)
{
const unsigned int TOP
= static_cast<int>(
std::sqrt( static_cast<double>( x ) )
) + 1;
for ( int i=2; i != TOP; ++i )
{
if (x % i == 0) return false;
}
return true;
}
int main()
{
unsigned int *l;
unsigned int n;
cout << "Ingrese tope de criba" << endl;
cin >> n;
l = new unsigned int[n];
initialize( l, n );
cout << "Esta es la lista" << endl;
show_list( l, n );
criba( l, n );  
cout << "Estos son los primos" << endl;
show_list( l, n );
}
void initialize( unsigned int *l, const unsigned int n)
{
for( int i = 0; i < n - 1; i++ )
*( l + i ) = i + 2;
}
void show_list( const unsigned int *l, const unsigned int n)
{
for( int i = 0; i < n - 1; i++ )
{
if( *( l + i ) != 0)
cout << l[i] << " - ";
}
cout << endl;
}
void setItem( unsigned int *l, const unsigned int n, const unsigned int p)
{
unsigned int i = 2;
while( p * i <= n)
{
*( l + (i * p - 2) ) = 0;
i++;
}
}
void criba( unsigned int *l, const unsigned int n)
{
for( int i = 0;  i * i <= n ; i++ )
if( IsPrime ( *( l + i) ) )
setItem( l, n, *(l + i) );      
}

0

En utilisant les règles de divisibilité des nombres premiers peuvent être trouvés dans la O(n) et c'est vraiment efficace Les règles de Divisibilité

La solution serait fondé sur chacun des chiffres du nombre...

#include<iostream>
using namespace std;
void main()
{
int num,i,j,prime;
cout<<"Enter the upper limit :";
cin>>num;
cout<<"Prime numbers till "<<num<<" are :2, ";
for(i=3;i<=num;i++)
{
prime=1;
for(j=2;j<i;j++)
{
if(i%j==0)
{
prime=0;
break;
}
}
if(prime==1)
cout<<i<<", ";
}
}

Voici ma mise en œuvre de Crible d'Eratosthène (pour les nombres premiers entre 2 & n)

#include <iostream>
int main (){
int n=0;
std::cout << "n = ";
std::cin >> n;
std::cout << std::endl;
if (n==0 || n==1){
std::cout << "No primes in this range" << std::endl;
return 0;
}
const int array_len = n-2+1;
int the_int_array[array_len];
for (int counter=2; counter <=n; counter++)
the_int_array[counter-2]=counter;
int runner = 0;
int new_runner = 0;
while (runner < array_len ){
if (the_int_array[runner]!=0){
new_runner = runner;
new_runner = new_runner + the_int_array[runner];
while (new_runner < array_len){
the_int_array[new_runner] = 0;
new_runner = (new_runner + the_int_array[runner]);
}
}
runner++;
}
runner = 0;
while (runner < array_len ){
if (the_int_array[runner]!=0)
std::cout << the_int_array[runner] << " ";
runner++;
}
std::cout << std::endl;
return 0;

}

#include "stdafx.h"
#include<iostream>
using namespace std;
void main()
{ int f =0;
for(int i=2;i<=100;i++)
{
f=0;
for(int j=2;j<=i/2;j++)
{ 
if(i%j==0)
{ f=1;
break;
}
}
if (f==0)
cout<<i<<" ";
}
system("pause");
}

c'est mon approche à partir d'un simple blog:

//Prime Numbers generation in C++
//Using for loops and conditional structures
#include <iostream>
using namespace std;
int main()
{
int a = 2;       //start from 2
long long int b = 1000;     //ends at 1000
for (int i = a; i <= b; i++)
{
for (int j = 2; j <= i; j++)
{
if (!(i%j)&&(i!=j))    //Condition for not prime
{
break;
}
if (j==i)             //condition for Prime Numbers
{
cout << i << endl;
}
}
}
}

- Voir plus à: http://www.programmingtunes.com/generation-of-prime-numbers-c/#sthash.YoWHqYcm.dpuf

De trouver si pas. est premier ou pas du C++:

#include<iostream>
#include<cmath>
using namespace std;
int main(){
int n, counter=0;
cout <<"Enter a number to check whether it is prime or not \n";
cin>>n;
for(int i=2; i<=n-1;i++) {
if (n%i==0) {
cout<<n<<" is NOT a prime number \n";
break;
}
counter++;
}
//cout<<"Value n is "<<n<<endl;
//cout << "number of times counter run is "<<counter << endl;
if (counter == n-2)
cout << n<< " is prime \n";
return 0;
}

0

Je l'ai fait en perl basée sur la réponse la plus populaire par ProdigySim la 2ème méthode. J'ai dû ajouter un break équivalent en perl, lastjuste après la print $i . " \n"; pour éviter de reproduire les nombres premiers deux fois.
```
#!/bin/perl
use strict;
for(my $i=2; $i < 100; $i++){
my $prime = 1;
for (my $j=2; $j*$j<=$i; $j++){
if ($i % $j == 0){
$prime = 0;
last;
}
if($prime) {
print $i . " \n";
last;
}
}
}
```

Un programme simple pour imprimer "N" nombres premiers. Vous pouvez utiliser N valeur de 100.

    #include  <iostream >
using  namespace  std;
int  main()
{
int  N;
cin  >>  N;
for (int  i =  2;  N > 0;  ++i)
{
bool  isPrime  =  true ;
for (int  j =  2;  j < i;  ++j)
{
if (i  % j ==  0)
{
isPrime  =  false ;
break ;
}
}
if (isPrime)
{
--N;
cout  <<  i  <<  "\n";
}
}
return  0;
}

voici un code simple pour l'impression de tous les nombres premiers jusqu'à un nombre donné n,

#include<iostream.h>
#include<conio.h>
void main()
{
clrscr();
int n,i,j,k;
cout<<"Enter n\n";
cin>>n;
for(i=1;i<=n;i++)
{   k=0;
for(j=1;j<=i;j++)
{
if((i%j)==0)
k++;
}
if(k==2)
cout<<i<<endl;
}
getch();
}

J'ai toujours l'utiliser (il est facile et rapide) :

#include <iostream>
using namespace std;
int i,j;
bool b[101];
int main( )
{
for(i=2;i<101;i++){
b[i]=true;
}
for(i=1;i<101;i++){
if(b[i]){
cout<<i<<" ";
for(j=i*2;j<101;j+=i) b[j]=false;
}
}
}

Ici, elle est sortie de ce code:
2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97

0

Le livre semble être "C++ pour les Ingénieurs et les Scientifiques."
écrit par Gary Bronson (googlé).

Est-ce une réponse possible? À mon humble avis, il est surprenant.

J'ai eu à lire la question (du livre) à quelques reprises.
Mon interprétation:

Pour chaque nombre N: 2 <= N < 100 vérifier si c'est le premier.

Comment? Pour chaque diviseur D: 2 <= D < sqrt(N) ,

si D divise N, N n'est pas premier,
si D > sqrt(N), N est premier.

Faire un essai:
```
N = 2, sqrt(2) ≈ 1.41, D = 2, 2 < 1.41 ?  no 2 > 1.41 ? yes 2 is prime.  
N = 3, sqrt(3) ≈ 1.73, D = 2, 2 < 1.73 ?  no 2 > 1.73 ? yes 3 is prime.  
N = 4, sqrt(4) = 2.00, D = 2, 2 < 2.00 ?  no 2 > 2.00 ?  no 4 is not prime.  
N = 5, sqrt(5) ≈ 2.24, D = 2, 2 < 2.24 ? yes 5 % 2 > 0? yes  
D = 3, 3 < 2.24 ?  no 3 > 2.24 ? yes 5 is prime.    
N = 6, sqrt(6) ≈ 2.45, D = 2, 2 < 2.45 ? yes 6 % 2 = 0  2 > 2.45 ? no 6 is not prime.
```
Aussi loin que je peux voir, c'est la façon dont les premiers devraient être trouvée,

pas avec un tamis (beaucoup plus rapide),

mais avec: la réponse est dans la question! Surprenant?

Vitesse? les nombres premiers < de 400 000 : moins de 10 secondes (sur ma montre, une rolex, je l'ai acheté sur le marché, le vendeur a dit que c'était un vrai, un vrai de vrai pour le prix de deux baguettes, avec 12 de vrais diamants).

Nous allons compter les nombres premiers (je ne vais pas vous montrer le code 😉 :
664579 nombres premiers < de 10 000 000 : 5 secondes.
```
#include "stdafx.h"
#include <math.h>
#include <iostream>
using namespace std;
int main()
{
double rt;
for (int d = 2, n = 2; n < 100; d = 2, n++)
{
for (rt = sqrt(n); d < rt; d++)
if (n % d == 0) break;
if (d > rt) cout << n << " ";
}
getchar();  //25 primes :-)
}
```
Supprimé une précédente réponse (comme d'autres réponses), un premier crible.

J'espère obtenir mon prochain "Nécromancien" insigne bientôt.

J'ai demandé à l'auteur: Dans votre livre: "C++ pour les F&S"
est un exercice sur les nombres premiers,[xrcs]...[/xrcs].
Il y a sept ans, il a été demandé à l': DONC/q/5200879

Il y A quelques jours, j'ai donné une réponse: DONC/un/49199435

Pensez-vous que c'est une solution raisonnable, ou peut-être la solution.

Il a répondu: Peter, je n'ai jamais vraiment avoir une solution spécifique à l'esprit
quand je fais les exercices,

donc je ne peux pas dire que j'ai votre solution exacte à l'esprit.
La joie de C++, c'est que l'on peut venir avec vraiment des solutions créatives et grand code,
car, à première vue, il semble que vous avez fait.

Merci pour l'envoi!

M. Bronson

Je suis allé à https://youtu.be/1175axY2Vvw

PS. Un tamis: https://pastebin.com/JMdTxbeJ

-1

Juste de l'essayer.
Il est facile, sans supplément de fonctions internes.

#include <iostream>
int prime(int n,int r){
for(int i=2;n<=r;i++){
if(i==2 || i==3 || i==5 || i==7){
std::cout<<i<<" ";
n++;
} else if(i%2==0 || i%3==0 || i%5==0 || i%7==0)
continue;
else {
std::cout<<i<<" ";
n++;
}
}
}
main(){
prime(1,25);
}

Essais par 2,3,5,7 est assez bon pour jusqu'à 120donc 100 est OK.

Il y a 25 nombres premiers ci-dessous 100un 30 ci-dessous 121 = 11*11.

Vous devez vous connecter pour publier un commentaire.