Primes

[Growl]

There is a integer n.
Find primes that is < than n and they can be expressed in the form 2^k-1.

Should I use something like this?

# include <iostream>
# include <math.h>
using namespace std;
int main()
{
  int num;
  bool prime;
  cout << "Please enter a positive integer" << endl;
  cin >> num;
  for(int i=3; i <= num; i++)
  {
    prime=true;
    for(int n=2; n<=i-1;n++)
    {
      if(i%n==0)
      {
        prime=false;
      }
    }
    if(prime)
    {
      cout<<i<< "IS PRIME" << endl;
    }
  }

  return 0;

[Generic]

Well that will work but it probably isn't all that efficient. Once you find a prime a you don't need to check any multiples of it, because you know they wont be prime. So for example, if you know 3 is prime then you know that 3*2, 3*3, 3*4, 3*5 etc... are not prime.

At the very least you can skip all the even numbers. Then you only have to check half as many.

[vlad from moscow]

I think the program will look "something like this".:)

[Chervil]

Firstly, instead of this for(int i=3; i <= num; i++) you need some way of generating members of the sequence 2^k-1 (where k is a positive integer) which are less than n.

Secondly, another refinement, you only need to test for division by values up to the square root of the value being tested. For smallish numbers this hardly matters, but when the number is large, could save many unnecessary repetitions.