Finding Primes

[cadencej]

Hey. I'm a newbie. I've been programming in C++ for about 2 weeks. I was wondering if anyone knows how to write a program to find primes between 1 and 1 million. Preferably under 10 Seconds, but not a requirement.

Thanks in advance.

~Cadence

[Bazzy]

You can try this algorithm: http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes

[coolProgramer5]

I'm with Bazzy use that algorithm it's good however, I don't think you will be able to find the primes in that range because when i tried my program crashed.

[tummychow]

Chances are, you just got an amazing overflow error.
@OP: I don't think you'll have an easy time finding that many primes in that timeframe, especially if you plan on outputting them. (And at your current experience level, I would doubt that you have the optimization techniques at your disposal to accelerate the runtime.) However, the sieve is probably the best algorithm in question. Beyond that, the runtime of your code is going to be largely out of your hands, as the compiler will do what it can to optimize your code and not much more.

[z05DSL3A]

_{http://www.cplusplus.com/forum/beginner/11654/#msg55499}

[cadencej]

Thanks guys. I knew about the Sieve of Eratosthenes, but I wasn't sure exactly how to implement that into C++ code. Grey Wolf, your code works for me, except for the fact that it doesn't show all of the primes. That's okay though, it gave me somewhere to start. Oh, and also, I just watched my teacher, run a program, which printed all the primes between 2 and a million in two seconds. Just thought that you might want to know.

Here is his code.

#include <iostream>
#include <stdlib.h>
using namespace std;


int main () {

int candidate,isprime,check;

cout << "2 ";
for (candidate=3;candidate<=999999;candidate=candidate+2) {
  isprime=1;
  for(check=3;check*check<=candidate;check=check+2) {
    if(candidate%check==0) {
      isprime=0;
      break;
    }
  }
  if (isprime==1) cout<<candidate<<" ";
}
return 0;
}

~Cadence

[jsmith]

And even that algorithm is hideously sub-optimal.

It should be easily doable to compute all the primes 2-1,000,000 in under 1 second.
(Output is another story).

[mcleano]

It should be easily doable to compute all the primes 2-1,000,000 in under 1 second.
(Output is another story).

Why is there such a performance impact?

[helios]

I/O is slow. Does this even need to be said?

[mcleano]

But why? I know the slowness exists but I don't have an explanation as to why.

[jsmith]

If you are using a graphical display, consider the amount of graphics processing it will take to render all that
text scrolling by in a window.

[helios]

Passing data between bridges has a relatively high overhead, not only because of the "bureaucracy" involved, but also due to the physical distance. To that, add the response time of specialized logic and mechanical parts in the devices. And then there's problematic virtual devices, as well. For example, printing to the console in Windows is hundreds of times slower than redirecting to the file system.
The one device that has been an exception to this rule is the screen. AGP and PCI-E video cards are connected to the Northbridge with very high bandwidths. Video RAM is almost a secondary main memory. (Furthermore, modern video cards are miniature [super]computers in themselves, but I digress.)

[prh]

Hi all,

Here's a program I wrote this morning that uses the sieve algorithm. My IDE (Borland 5.02) is a little old, but the code works. I put in two loops, one that finds the primes and one that prints them to demonstrate the slow output. Enjoy.

#include <iostream.h>
#include <iomanip.h>
#include <conio.h>

#define TRUE 1
#define FALSE 0
int main( )
{
   int sieveSize;
   cout << "Enter sieve size: ";
   cin >> sieveSize;

   char* sievePtr = new char[sieveSize];
   if ( sievePtr == 0 ) {
      cout << "Sieve allocation failed!" << endl;
      getch();
      return 1;
   }//endif
   char* endPtr = sievePtr + sieveSize;

   for ( char* sPtr = sievePtr; sPtr < endPtr; sPtr++) *sPtr = TRUE;

   for ( char* sPtr = sievePtr + 2; sPtr < endPtr; sPtr++) {
      if ( *sPtr ) {
         int offset = sPtr - sievePtr;
         for ( char* oPtr = sPtr + offset; oPtr < endPtr; oPtr += offset) {
            *oPtr = FALSE;
         }//endfr
      }//endif
   }//endfr

   int n = 0;
   for ( char* sPtr = sievePtr + 2; sPtr < endPtr; sPtr++) {
      if ( *sPtr ) {
         cout << setw( 10 ) << ( sPtr - sievePtr );
         if ( !( ++n % 10 ) ) cout << endl;
      }//endif
   }//endfr

   delete[] sievePtr;

   getch();
   return 0;
}//endmn

[chrisname]

Why have you #define'd TRUE and FALSE? Why not just use true and false? You're clearly using C++ as you've got new and delete.

[prh]

No good reason. I wrongly assumed my old compiler didn't know about them.

[jsmith]

Ok, fine. Here's my version of the above program.

#include <algorithm>
#include <boost/lambda/lambda.hpp>
#include <deque>
#include <iostream>

int main() {
    std::deque<unsigned> p( 1, 2 );
    for( unsigned cand = 3; p.size() < 100; ++cand )
        if( std::find_if( p.begin(), p.end(), cand % boost::lambda::_1 == 0 ) == p.end() )
            p.push_back( cand );

    std::for_each( p.begin(), p.end(), std::cout << "List of first " << p.size()
        << " primes:\n" << boost::lambda::_1 << '\n' );
}

It will generate and output the first 100 primes. If you want a different number of primes, then
change the 100 in the first for() loop to whatever value you like.

[coolProgramer5]

here is mine.

#include <stdio.h>
#include <math.h>                      

#define N 300               
 
bool isPrime(bool flag[]); 
int main()                                    
{
      bool flag[N];
    isPrime(flag);
    getchar();
    return 0;
}
bool isPrime(bool flag[])
{
  int  prime[N + 1];                 
  long n;                             
  long s;                            
  long t = 0;                        

  prime[0] = 0;                       
  prime[1] = 0;
  for (n = 2; n <= N; n++)       
    prime[n] = 1;

  for (n = 2; n <= sqrt(N); n++) 
  {       
    if (prime[n])
    {                     
      for (s = 2; s <= (N / n); s++)
      {  
        prime[s * n] = 0;
        }
        }
        }

  for (n = 2; n <= N; n++)
  {
    if (prime[n])  
    {
      
      printf("%7ld\t", n);
      t = (t + 1) % 10;
      
      if (t == 0)
      {
        printf("\n");
        }
    }
}
  printf("\n");
}

[coolProgramer5]

And please dont remind me about the horrible indenting. I wrote this last year.

[chrisname]

@prh,
fair enough. If you wanted an awesome boolean variable in C;

#ifndef _BOOLEAN
#define _BOOLEAN
typedef enum {
    False = 0,
    True
}   boolean;
#endif 

I like jsmith's one best