Printing prime numbers from 1 through 100

Question

This c   code prints out the following prime numbers    3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97   But I don t think that s the way my book wants it to be written  It mentions something about square root of a number  So I did try changing my 2nd loop to for  int j 2  j lt sqrt i   j    but it did not give me the result I needed   How would I need to change this code to the way my book wants it to be   int main           for  int i 2  i lt 100  i             for  int j 2  j lt i  j                          if  i   j    0                   break              else if  i    j 1                  cout  lt  lt  i  lt  lt                         return 0         A prime integer number is one that has   exactly two different divisors     namely 1 and the number itself  Write    run  and test a C   program that    finds and prints all the prime numbers   less than 100   Hint  1 is a  prime   number  For each number from 2 to 100    find Remainder   Number   n  where n   ranges from 2 to sqrt number     If n   is greater than sqrt number   the   number is not equally divisible by n     Why  If any Remainder equals 0  the   number is no a prime number

User · Answer

The book seems to be  C   for Engineers and Scientists   written by Gary Bronson  googled it   Is this a possible answer  IMHO it s surprising   I had to read the question  from the book  a few times   My interpretation  For each number N  2  lt   N  lt  100 check whether it s prime  How  For each divisor D  2  lt   D  lt  sqrt N    if D divides N  N is not prime  if D   sqrt N   N is prime   Give it a try    N   2  sqrt 2     1 41  D   2  2  lt  1 41    no 2  gt  1 41   yes 2 is prime    N   3  sqrt 3     1 73  D   2  2  lt  1 73    no 2  gt  1 73   yes 3 is prime    N   4  sqrt 4    2 00  D   2  2  lt  2 00    no 2  gt  2 00    no 4 is not prime    N   5  sqrt 5     2 24  D   2  2  lt  2 24   yes 5   2  gt  0  yes                          D   3  3  lt  2 24    no 3  gt  2 24   yes 5 is prime      N   6  sqrt 6     2 45  D   2  2  lt  2 45   yes 6   2   0  2  gt  2 45   no 6 is not prime    As far as I can see  that s how the primes should be found  not with a sieve  much  much faster   but with  the answer is in the question  Surprising   Speed  primes  lt  400 000   less than 10 seconds  on my watch  a rolex  I bought it on the market  the seller said it was a real one  a real one for the price of two baguettes  with 12 real diamonds as well   Let s count the primes  I m not going to show code       664579 primes  lt  10 000 000   5 seconds    include  stdafx h   include  lt math h gt   include  lt iostream gt  using namespace std  int main         double rt      for  int d   2  n   2  n  lt  100  d   2  n                  for  rt   sqrt n   d  lt  rt  d                if  n   d    0  break          if  d  gt  rt  cout  lt  lt  n  lt  lt                 getchar        25 primes  -      Deleted an earlier answer with  like other answers  a prime-sieve  Hopefully I get my next  Necromancer  badge soon     I asked the author  In your book   C   for E amp S  is an exercise about prime numbers  xrcs      xrcs   Seven years ago it was asked at  SO q 5200879 A few days ago I gave an answer  SO a 49199435 Do you think it is a reasonable solution  or perhaps the solution   He replied  Peter  I never really have a specific solution in mind when I am making up the exercises  so I can   t  say I had your exact solution in mind  The joy of C   is that one can come up with really creative solutions and great code  as  on first glance  it looks like you have done  Thanks for sending it  Dr  Bronson  I went to https   youtu be 1175axY2Vvw    PS  A sieve  https   pastebin com JMdTxbeJ

User · Answer

Using Sieve of Eratosthenes logic  I am able to achieve the same results with much faster speed   My code demo VS accepted answer    Comparing the count  my code takes significantly lesser iteration to finish the job  Checkout the results for different N values in the end   Why this code performs better than already accepted ones   - the even numbers are not checked even once throughout the process   - both inner and outer loops are checking only within possible limits  No extraneous checks   Code   int N   1000    Print primes number from 1 to N vector lt bool gt  primes N  true   for int i   3  i i  lt  N  i    2        Jump of 2     for int j   3  j i  lt  N  j  2      Again  jump of 2         primes j i    false          if N  gt   2  cout  lt  lt   2    for int i   3  i  lt  N  i  2            Again  jump of 2     if primes i     true  cout  lt  lt  i  lt  lt            For N   1000  my code takes 1166 iterations  accepted answer takes 5287  4 5 times slower   For N   10000  my code takes 14637 iterations  accepted answer takes 117526  8 times slower   For N   100000  my code takes 175491 iterations  accepted answer takes 2745693  15 6 times slower

User · Answer

this is my approach from a simple blog     Prime Numbers generation in C     Using for loops and conditional structures  include  lt iostream gt  using namespace std   int main     int a   2          start from 2 long long int b   1000        ends at 1000  for  int i   a  i  lt   b  i        for  int j   2  j  lt   i  j           if    i j  amp  amp  i  j        Condition for not prime                       break                 if  j  i                condition for Prime Numbers                         cout  lt  lt  i  lt  lt  endl                      - See more at  http   www programmingtunes com generation-of-prime-numbers-c  sthash YoWHqYcm dpuf

User · Answer

include  stdafx h   include lt iostream gt  using namespace std  void main     int f  0   for int i 2 i lt  100 i           f 0     for int j 2 j lt  i 2 j               if i j  0         f 1         break               if  f  0    cout lt  lt i lt  lt         system  pause

User · Answer

include lt iostream gt  using namespace std  void main             int num i j prime      cout lt  lt  Enter the upper limit         cin gt  gt num      cout lt  lt  Prime numbers till   lt  lt num lt  lt   are  2          for i 3 i lt  num i                  prime 1          for j 2 j lt i j                          if i j  0                                prime 0                  break                                  if prime  1              cout lt  lt i lt  lt

User · Answer

Here is my implementation of Sieve of Eratosthenes  for primes between 2  amp  n    include  lt iostream gt   int main     int n 0  std  cout  lt  lt   n      std  cin  gt  gt  n  std  cout  lt  lt  std  endl   if  n  0    n  1       std  cout  lt  lt   No primes in this range   lt  lt  std  endl      return 0      const int array len   n-2 1   int the int array array len   for  int counter 2  counter  lt  n  counter        the int array counter-2  counter    int runner   0  int new runner   0   while  runner  lt  array len        if  the int array runner   0           new runner   runner          new runner   new runner   the int array runner            while  new runner  lt  array len              the int array new runner    0             new runner    new runner   the int array runner                    runner       runner   0   while  runner  lt  array len        if  the int array runner   0          std  cout  lt  lt  the int array runner   lt  lt           runner       std  cout  lt  lt  std  endl  return 0

User · Answer

If a number has divisors  at least one of them must be less than or equal to the square root of the number  When you check divisors  you only need to check up to the square root  not all the way up to the number being tested

User · Answer

I did it in perl based on the most popular answer by ProdigySim s 2nd method  I had to add a break equivalent in perl  last  right after the print  i      n   to avoid outputting the primes twice      bin perl use strict   for my  i 2   i  lt  100   i          my  prime   1       for  my  j 2   j  j lt   i   j             if   i    j    0                prime   0              last                    if  prime                print  i      n               last

User · Answer

If j is equal to sqrt i  it might also be a valid factor  not only if it s smaller   To iterate up to and including sqrt i  in your inner loop  you could write   for  int j 2  j j lt  i  j       Compared to using sqrt i  this has the advantage to not need conversion to floating point numbers

User · Answer

here is a simple code for printing all the prime numbers until given number n    include lt iostream h gt   include lt conio h gt   void main     clrscr    int n i j k  cout lt  lt  Enter n n   cin gt  gt n   for i 1 i lt  n i        k 0    for j 1 j lt  i j            if  i j   0      k           if k  2    cout lt  lt i lt  lt endl    getch

User · Answer

actually the better solution is to use  A prime sieve or prime number sieve  which   is a fast type of algorithm for finding primes     wikipedia  The simple  but not faster  algorithm is called  sieve of eratosthenes  and can be done in the following steps from wikipedia again          Create a list of consecutive integers from 2 to n   2  3  4       n     Initially  let p equal 2  the first prime number    Starting from p  count up in increments of p and mark each of these numbers greater than p itself in the list  These numbers will be   2p  3p  4p  etc   note that some of them may have already been marked    Find the first number greater than p in the list that is not marked  If there was no such number  stop  Otherwise  let p now equal   this number  which is the next prime   and repeat from step 3

User · Answer

Just try this   It s  easy without any extra builtin functions    include  lt iostream gt   int prime int n int r      for int i 2 n lt  r i         if i  2    i  3    i  5    i  7         std  cout lt  lt i lt  lt            n          else if i 2  0    i 3  0    i 5  0    i 7  0        continue      else         std  cout lt  lt i lt  lt            n                  main       prime 1 25       Testing by 2 3 5 7 is good enough for up to 120  so 100 is OK   There are 25 primes below 100  an 30 below 121   11 11

User · Answer

To find whether no  is prime or not C       include lt iostream gt   include lt cmath gt   using namespace std  int main     int n  counter 0   cout  lt  lt  Enter a number to check whether it is prime or not  n   cin gt  gt n     for int i 2  i lt  n-1 i          if  n i  0          cout lt  lt n lt  lt   is NOT a prime number  n         break            counter                            cout lt  lt  Value n is   lt  lt n lt  lt endl        cout  lt  lt   number of times counter run is   lt  lt counter  lt  lt  endl      if  counter    n-2        cout  lt  lt  n lt  lt    is prime  n      return 0

User · Answer

I always use this one  it s easy and fast      include  lt iostream gt  using namespace std   int i j  bool b 101    int main          for i 2 i lt 101 i             b i  true            for i 1 i lt 101 i             if b i                cout lt  lt i lt  lt                  for j i 2 j lt 101 j  i  b j  false                      Here is output of this 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

User · Answer

This is my very simple c   program to list down the prime numbers in between 2 and 100   for int j 2 j lt  100   j        int i 2      for  i lt  j-1 i                  if j i    0              break             if i  j  amp  amp  i    2          cout lt  lt j lt  lt endl

User · Answer

While this is relatively more production grade prime number generator  it is still valid to use for finding prime numbers from 1 through 100  The code uses Miller-Rabin Primality Test to achieve calculate prime numbers  Since it is probabilistic method  the accuracy increases with value of k  While the focus is on readability of code rather than speed  on AWS r5 2xlarge instance it took 3 791s for prime number until 1 000 000       C   program to print all primes smaller than or equal to     n using Miller-Rabin Primality Test    Reference  https   en wikipedia org wiki Miller E2 80 93Rabin primality test    It is not particularly to optimized     since focus is readability    Compile  g    -std c  17 -o prime prime c   -ltbb    include  lt execution gt   include  lt iostream gt   include  lt math h gt  using namespace std    int power unsigned long int x  unsigned long y  unsigned long p       int res   1      x   x   p      while  y  gt  0            if  y  amp  1              res    res   x    p          y   y  gt  gt  1          x    x   x    p            return res     bool millerTest unsigned long d  unsigned long n        unsigned long a   2   rand       n - 4        unsigned long x   power a  d  n        if  x    1     x    n - 1          return true       while  d    n - 1           x    x   x    n          d    2          if  x    1  return false          if  x    n - 1  return true             return false     bool isPrime unsigned long n  int k        if  n  lt   1    n    4  return false      if  n  lt   3  return true       unsigned long int d   n - 1      while  d   2    0          d    2      for int i   0  i  lt  k  i             if   millerTest d  n               return false            return true        int main           int n   1000000      int k   200       vector lt unsigned long gt  primeN n       iota primeN begin    primeN end    1        vector lt bool gt  isPrimeV n          transform execution  par          primeN begin    primeN end             isPrimeV begin              k  unsigned long x  - gt  bool               return isPrime x  k                    int count   accumulate isPrimeV begin    isPrimeV end    0     int d  bool v           if  v    true  return d    1  else return d              cout  lt  lt  count  lt  lt  endl       return 0

User · Answer

Three ways   1   int main           for  int i 2  i lt 100  i             for  int j 2  j j lt  i  j                          if  i   j    0                   break              else if  j 1  gt  sqrt i                     cout  lt  lt  i  lt  lt                                         return 0      2   int main           for  int i 2  i lt 100  i                   bool prime true          for  int j 2  j j lt  i  j                          if  i   j    0                                 prime false                  break                                         if prime  cout  lt  lt  i  lt  lt                 return 0      3    include  lt vector gt  int main         std  vector lt int gt  primes      primes push back 2       for int i 3  i  lt  100  i                  bool prime true          for int j 0 j lt primes size    amp  amp  primes j  primes j   lt   i j                          if i   primes j     0                                prime false                  break                                  if prime                         primes push back i               cout  lt  lt  i  lt  lt                            return 0      Edit  In the third example  we keep track of all of our previously calculated primes  If a number is divisible by a non-prime number  there is also some prime  lt   that divisor which it is also divisble by  This reduces computation by a factor of primes in range total range

User · Answer

I check if a number is prime or not with the following code  of course using sqrt     bool IsPrime const unsigned int x      const unsigned int TOP     static cast lt int gt         std  sqrt  static cast lt double gt   x             1     for   int i 2  i    TOP    i           if  x   i    0  return false        return true      I use this method to determine the primes    include  lt iostream gt   using std  cout  using std  cin  using std  endl    include  lt cmath gt   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 lt int gt         std  sqrt  static cast lt double gt   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  lt  lt   Ingrese tope de criba   lt  lt  endl      cin  gt  gt  n       l   new unsigned int n        initialize  l  n         cout  lt  lt   Esta es la lista   lt  lt  endl      show list  l  n         criba  l  n           cout  lt  lt   Estos son los primos   lt  lt  endl      show list  l  n       void initialize  unsigned int  l  const unsigned int n        for  int i   0  i  lt  n - 1  i                l   i     i   2     void show list  const unsigned int  l  const unsigned int n        for  int i   0  i  lt  n - 1  i                   if     l   i      0              cout  lt  lt  l i   lt  lt    -              cout  lt  lt  endl     void setItem  unsigned int  l  const unsigned int n  const unsigned int p        unsigned int i   2      while  p   i  lt   n                   l    i   p - 2      0          i             void criba  unsigned int  l  const unsigned int n        for  int i   0   i   i  lt   n   i          if  IsPrime      l   i              setItem  l  n    l   i

User · Answer

Using the rules of divisibility prime numbers can be found out in O n  and it s really effecient Rules of Divisibility  The solution would be based on the individual digits of the number

User · Answer

Finding primes up to a 100 is especially nice and easy       printf  2 3                               first two primes are 2 and 3     int m5   25  m7   49  i   5  d   4      for    i  lt  25  i     d 6-d                  printf   d    i                       all 6-coprimes below 5 5 are prime           for    i  lt  49  i     d 6-d                  if  i    m5  printf   d    i           if  m5  lt   i   m5    10                no multiples of 5 below 7 7 allowed            for    i  lt  100  i     d 6-d               from 49 to 100                if  i    m5  amp  amp  i    m7  printf   d    i           if  m5  lt   i   m5    10                  sieve by multiples of 5          if  m7  lt   i   m7    14                                      and 7  too         The square root of 100 is 10  and so this rendition of the sieve of Eratosthenes with the 2-3 wheel uses the multiples of just the primes above 3 that are not greater than 10 -- viz  5 and 7 alone  -- to sieve the 6-coprimes below 100 in an incremental fashion

User · Answer

It s fine to change your for loop to for  int j 2  j lt  sqrt i   j    but then you also need to change something else  Looking specifically at your print condition    else if  i    j 1          cout  lt  lt  i  lt  lt           why will that never be triggered if you only iterate up to sqrt i   Where can you move the cout to to change this   Hint  you may want to move the print out of the loop and then make use of some type of flag variable

User · Answer

A simple program to print  N  prime numbers  You can use N value as 100        include   lt iostream  gt      using  namespace  std       int  main                 int  N          cin   gt  gt   N          for  int  i    2   N  gt  0     i                        bool  isPrime     true               for  int  j    2   j  lt  i     j                                if  i    j     0                                        isPrime     false                       break                                               if  isPrime                                --N                  cout   lt  lt   i   lt  lt     n                                   return  0

[c++] Printing prime numbers from 1 through 100

Examples related to c++

Examples related to c

Examples related to algorithm

Examples related to primes