Prime

[porkshop]

This program should find prime numbers but I don't know what is going wrong...

 #include <iostream>

int main() {
	int num;
	for (num = 1; num = 100; num++); {
		int div, rem = 0; // number, divider, remainder (number starts at 1)

		for (div = 2; div == num; div++); { // divider goes through every possible number up to the possible prime
			if (num % div == 0) {     // if remainder is 0
				std::cout << "Test\n";
			}
			else {
				rem++;
			}
			if (rem > 1) { // if num has successfulle been divided more than once

			}
			else {
				std::cout << num << "\n"; // if not, the number is prime

			}
		}
	}
}

[JLBorges]

#include <iostream>

int main() {

    // note the structure of the for loop
    // (also note that there is no ; after the closing parenthesis)
    for( int num = 2; num < 100; ++num ) { // for every number from 2 to 99

        bool is_prime = true ; // prime if the number is not divisible

        // check divisibility with every possible number up to the possible prime
        for( int div = 2; div < num; ++div )
            if( num%div == 0 ) is_prime = false ; // not prime if remainder is 0
        // note: we can break out of this loop immediately if it is not a prime
        // note: we need to check divisibility only up to half (square root) of the number
        // you may ignore these two niceties for now

        if(is_prime) std::cout << num << '\n' ; // if the number is prime, print it
    }
}

[Grime]

for (num = 1; num = 100; num++); { ... }
should be
for (num = 1; num <= 100; num++) { ... }

for (div = 2; div == num; div++); { ... }
should be
for (div = 2; div <= num; div++) { ... }

(num % div == 0) is true when 'num' is evenly divisible by 'div'. So 'rem' should be incremented under the if-block not under the else-block.

		if (rem > 1) { // if num has successfulle been divided more than once
// Grime -> "btw you could write if(r == 1) and use only one statement" 
		}
		else {
				std::cout << num << "\n"; // if not, the number is prime

		}

^^ Should be outside the inner for-loop and inside the outer for-loop otherwise you would be printing every iteration of the inner for-loop, which is not what you want.

[keskiverto]

What is the condition of the loop on line 5?

What is the condition of the loop on line 8?

Why is the condition (lines 15-21) inside the loop?

[porkshop]

Ok, thanks! I understand now.

[porkshop]

Is there a way to have an output that shows the number of primes per second? I would like to see the difference in speed between checking for every possible divider < the number and < sqrt of the number.

[JLBorges]

#include <iostream>
#include <ctime>
#include <cmath>

int main() {

    // compute primes up to 25'000
    const int UBOUND = 25'000 ;

    // original
    {
        // https://en.cppreference.com/w/cpp/chrono/c/clock
        const auto start = std::clock() ;

        int num_primes = 0 ;

        for( int num = 2; num < UBOUND ; ++num ) {

            bool is_prime = true ;

            for( int div = 2; div < num; ++div ) if( num%div == 0 ) is_prime = false ;

            if(is_prime) ++num_primes ;
        }

        const auto end = std::clock() ;
        std::cout << "brute force: " << num_primes << " primes found in "
                  << (end-start) * 1000.0 / CLOCKS_PER_SEC
                  << " processor milliseconds.\n" ;
    }

    // sqrt + check only odd numbers > 2
    {
        const auto start = std::clock() ;

        int num_primes = 1 ; // two is prime

        for( int num = 3; num < UBOUND ; num += 2 ) { // check only odd numbers

            bool is_prime = true ;

            const int root = std::sqrt(num) + 1 ;
            // break out of the loop immediately if it is not a prime
            for( int div = 2; is_prime && div <= root; ++div ) if( num%div == 0 ) is_prime = false ;

            if(is_prime) ++num_primes ;
        }

        const auto end = std::clock() ;
        std::cout << "somewhat faster: " << num_primes << " primes found in "
                  << (end-start) * 1000.0 / CLOCKS_PER_SEC
                  << " processor milliseconds.\n" ;
    }
    
    // for something even faster, see: https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes
} 

echo && g++ -std=c++17 -O3 -march=native -Wall -Wextra -pedantic-errors main.cpp && ./a.out 
echo && clang++ -std=c++17  -stdlib=libc++ -O3 -march=native -Wall -Wextra -pedantic-errors main.cpp -lsupc++ && ./a.out

brute force: 2762 primes found in 1442.57 processor milliseconds.
somewhat faster: 2762 primes found in 2.2 processor milliseconds.

brute force: 2762 primes found in 1454.62 processor milliseconds.
somewhat faster: 2762 primes found in 2.318 processor milliseconds.

http://coliru.stacked-crooked.com/a/3530c0f655ae97ce

[porkshop]

Thank you! This went completely over my head, do you know any good interactive c++ lessons on the internet apart from codecademys?

[Grime]

Can always pirate C++ books online ;]
thenewboston/Derek Banas have made good tutorials on C++ on YouTube BTW.
Lastly check out learncpp.com which has a nice (text) tutorial, if you're interested.

[JLBorges]

No, I'm not aware of any (good or bad) interactive c++ lessons on the net.
Perhaps someone else would be able to give you a better answer.

The code is not as complicated as it appears to you right now; come back to it after you have been programming for a little while, and it should be quite easy to understand.

[porkshop]

Ok, thanks for all the help! Is there a way that I can make it have a specified amount of time to search for primes, for example: how many primes can it find when t = 10 sec.

[lastchance]

With full optimisation (-O3):

Found 5761455 primes in 1.092 seconds

The first 20 are: 2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71

#include <iostream>
#include <cmath>
#include <ctime>
#include <valarray>
#include <vector>
using namespace std;

vector<int> sieve( int N )
{
   valarray<bool> A( true, 1 + N );
   for ( int i = 2; i <= sqrt( N + 0.5 ); i++ ) if ( A[i] ) A[ slice( i+i, N/i-1, i ) ] = false;
   vector<int> P;
   for ( int i = 2; i <= N; i++ ) if ( A[i] ) P.push_back( i );
   return P;
}

int main()
{
   const int N = 100000000;
   
   clock_t t0 = clock();
   vector<int> primes = sieve( N );
   double t = (double)( clock() - t0 ) / CLOCKS_PER_SEC;

   cout << "Found " << primes.size() << " primes in " << t << " seconds\n\n";

   const int num = 20;
   cout << "The first " << num << " are: ";
   for ( int i = 0; i < num; i++ ) cout << primes[i] << " ";
}

[MikeStgt]

If it is about speed, use https://primesieve.org/ as role model.
If it is about Sieve of Eratosthenes, there is nothing like SQRT in his algorithm. But compiled C/C++ is so fast that even a doubtful one is good enough for the first bunch of primes.

I suggest:

/* SoE.cpp: Sieve of Eratosthenes */
#include <iostream>		/* cout, cin, endl */
#include <ctime>		/* clock */
using namespace std;

	unsigned long const z(100000000);
	bool p[z];

int main()
{
	unsigned long n, c(1), i;

	clock_t t0 = clock();		/* time(R) */
	for (n = 3; n <= z; n+=2)
	{ p[n] = true; }		/* define candidates */

	for (n = 3; n <= z; n+=2)
	{
		if (p[n])		/* candidate is prime */
		{
			c += 1;		/* increment coutner */
			if (n <= z/n)	/* no overflow pls */
			{
				for (i = n*n; i <= z; i += n+n)
				{
					p[i] = false;	/* sieve out multiple */
				}
			}
		}
	}
	double te = (double)( clock() - t0 ) / CLOCKS_PER_SEC;  /* time(E) */

	cout << "From 1.." << z << " found " << c << " primes in " << te << " seconds." << endl;
}

Output from www.cpp.sh:

From 1..100000000 found 5761455 primes in 0.898246 seconds.

Question: I tried to initialize bool p[z] by bool p[z] { };, alas the compiler did not like it. Why?

There are more prime sieves, for example Atkin and Sundaram. For the later I need to translate do n = j + k by k for j while n <= z to C++. May I combine two end criteria in a for-loop? Suggestions welcome.

(Edit: added run time measurement and output)

[keskiverto]

Question: I tried to initialize bool p[z] by bool p[z] { };, alas the compiler did not like it. Why?

What did it say, exactly?
(I've never seen compiler to output: "Error: I don't like this code.")

The brace-initialization syntax was added in C++11.
The GCC (except the latest versions) defaults to C++03 (with GNU extensions),
even though it does have support for newer standard(s). See option -std

[lastchance]

Slightly quicker sieving odd multiples only. With -O3 optimisation:

Found 5761455 primes in 0.89835 seconds

The first 20 are: 2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71  

#include <iostream>
#include <cmath>
#include <ctime>
#include <valarray>
#include <vector>
using namespace std;

vector<int> sieve( int N )
{
   valarray<bool> A( true, 1 + N );
   for ( int i = 3; i <= sqrt( N + 0.5 ); i += 2 )                   // Only worry about odd numbers
   {
      if ( A[i] )
      {
         int isq = i * i, ii = i + i;
         A[ slice( isq, ( N - isq ) / ii + 1, ii ) ] = false;        // Mark odd multiples (and use symmetry)
      }
   }
   vector<int> P = { 2 };                                            // 2 is the only even prime
   for ( int i = 3; i <= N; i += 2 ) if ( A[i] ) P.push_back( i );   // Include odd primes
   return P;
}

int main()
{
   const int N = 100000000;
   clock_t t0 = clock();
   vector<int> primes = sieve( N );
   double t = (double)( clock() - t0 ) / CLOCKS_PER_SEC;

   cout << "Found " << primes.size() << " primes in " << t << " seconds\n\n";

   const int num = 20;
   cout << "The first " << num << " are: ";
   for ( int i = 0; i < num; i++ ) cout << primes[i] << " ";
}

[MikeStgt]

Reply to keskiverto (http://www.cplusplus.com/forum/beginner/250568/#msg1103519)

What did it say, exactly?
(I've never seen compiler to output: "Error: I don't like this code.")

Sorry, I am not only new to C++ but to forum habits too.

bool p[z] { };
results in

1>c:\users\...\visual studio 2010\projects\soe\soe\eratosthenes.cpp(7): error C2470: 'p' : looks like a function definition, but there is no parameter list; skipping apparent body

I just adopted to type bool what I found in the tutorials about arrays: http://www.cplusplus.com/doc/tutorial/arrays/

My goal is not to compute well known prime numbers but taking my first steps into still foggy C++ by migrating simple procedures to it like this one, also as simple as possible:

/* SIEVE EXEC: Sieb des Eratosthenes                                  */
   p. = 1                             /* Indexfeld                    */
   z = 999999                         /* mehr nicht fürs Erste        */
   say 2                              /* einzige gerade Primzahl      */
   do n = 3 to z by 2                 /* teste ab 3 jede Ungerade     */
      if p.n then do                  /* wenn prim, dann...           */
         say n                        /* ausgeben                     */
         do i = n * n to z by 2 * n   /* gehe bis Feldende und        */
            p.i = 0                   /* siebe Multiple aus           */
         end
      end
   end

This is REXX running on z/VM and other platforms. (To keep it simple here one wheel factor only: 2)

[MikeStgt]

Reduced the overhead from sqrt(z) to z around c += 1; for counting primes by adding another loop.

#include <iostream>		/* cout, cin, endl */
#include <ctime>		/* clock */
using namespace std;

	unsigned long const z(100000000);
	bool p[z+1];   // C++ arrays are 0-base numbered

int main()
{
	unsigned long n, c(1), i;

	clock_t t0 = clock();		/* time(R) */
	for (n = 3; n <= z; n+=2)
	{ p[n] = true; }		/* define candidates */

	for (n = 3; n*n <= z; n+=2)
	{
		if (p[n])		/* candidate is prime */
		{
			c += 1;		/* increment coutner */
			if (n <= z/n)	/* no overflow pls */
			{
				for (i = n*n; i <= z; i += n+n)
				{
					p[i] = false;	/* sieve out multiple */
				}
			}
		}
	}
	for (n = n + 2; n <= z; n+=2)  // sieving done, all remaining are prime
	{
		if (p[n])		/* candidate is prime */
		{
			c += 1;		/* increment coutner */
		}
	}
	double te = (double)( clock() - t0 ) / CLOCKS_PER_SEC;  /* time(E) */

	cout << "From 1.." << z << " found " << c << " primes in " << te << " seconds." << endl;
}

Result on cpp.sh with option -O3:

From 1..100000000 found 5761455 primes in 0.795668 seconds.

Alas, code is drifting away from the clear, transparent simplicity of my original in REXX (which is close to pseudo code). Next optimizing step would be the use of a {2, 3}- or {2, 3, 5}-wheel.

Edit: I could not achieve any gain with a {2, 3}-wheel.
Edit: The elements of an array in C++ are numbered from 0 on, so... (see code)

[MikeStgt]

I (beginner) know now how to initialize a bool array. At least I can set all to false, alas I do not know how to define it from the beginning to be all true. No harm, I inversed the logic what is prime and which are mulitpe of primes.

#include <iostream>		/* cout, cin, endl */
#include <ctime>		/* clock */
using namespace std;

	unsigned long const z(100000000);
	bool m[z+1] = { };		/* arrays in C++ are 0 based */

int main()
{
	unsigned long n, c(1), i;

	clock_t t0 = clock();		/* time(R) */

	for (n = 3; n*n <= z; n+=2)	/* only up to sqrt(z) */
	{
		if (!m[n])		/* candidate is not multiple = prime */
		{
			c += 1;		/* increment counter */
			for (i = n*n; i <= z; i += n+n)
			{
				m[i] = true;	/* sieve out multiple */
			}
		}
	}

/* sieving is done, all remaining are prime */
	for (n = n + 2; n <= z; n+=2)
		if (!m[n])		/* candidate is prime */
			c += 1;		/* increment coutner */

	double te = (double)( clock() - t0 ) / CLOCKS_PER_SEC;  /* time(E) */

	cout << "From 1.." << z << " found " << c << " primes in " << te << " seconds." << endl;
}

Result on www.cpp.sh with optimization level -O1 (moderate):

From 1..100000000 found 5761455 primes in 0.743417 seconds.

Result of Primesieve 7.4 from https://primesieve.org:

Prime numbers:	5761455
Elapsed time:	0.01 sec

So my suggestion is still a candidate for improvement.

Edit: with n*n <= z as limit for sieving loop no need to test for overflow within loop.

[lastchance]

Works better with vector<bool>. With -O3 optimisation:

Found 5761455 primes in 0.539761 seconds

The first 20 are: 2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71  

#include <iostream>
#include <cmath>
#include <ctime>
#include <vector>
using namespace std;

vector<int> sieve( int N )
{
   vector<bool> A( 1 + N, true );
   int imax = sqrt( N + 0.5 );
   for ( int i = 3; i <= imax; i += 2 )                   // Only worry about odd numbers
   {
      if ( A[i] )
      {
         int ii = i + i;
         for ( int j = i * i; j <= N; j += ii ) A[j] = false;
      }
   }
   vector<int> P = { 2 };                                            // 2 is the only even prime
   for ( int i = 3; i <= N; i += 2 ) if ( A[i] ) P.push_back( i );   // Include odd primes
   return P;
}

int main()
{
   const int N = 100000000;
   clock_t t0 = clock();
   vector<int> primes = sieve( N );
   double t = (double)( clock() - t0 ) / CLOCKS_PER_SEC;

   cout << "Found " << primes.size() << " primes in " << t << " seconds\n\n";

   const int num = 20;
   cout << "The first " << num << " are: ";
   for ( int i = 0; i < num; i++ ) cout << primes[i] << " ";
}

[jonnin]

diminishing returns but
const int ii = i << 1; //any better? same as *2 same as i+i.. probably no savings here.

and maybe bigger, add a P.reserve() to it, is that helpful?