Programming Forums - Calculate prime numbers

Programming Forums (http://www.programmingforums.org/forumindex.php)

- Show Off Your Open Source Projects (http://www.programmingforums.org/forum52.html)

- - Calculate prime numbers (http://www.programmingforums.org/showthread.php?t=11224)

Calculate prime numbers

Hope it hasn't been done before D:
But anyway, I did it all by myself. Took about two to three days of on and off thinking to figure out how to get it working. It seems to work correctly, comments and criticism of my probably horrible code are welcome.

http://pi.monkeh.net/prime.cpp

Try using 121 for your input ;)

121 doesn't work

Also, this code seems odd:

        while (n%2==0)            // tests for even number. if it's even, it's not going to be prime.

                                  // 2 is indeed prime, but n starts at 10 n_n

        {

           cout << n << " is even" << endl;

           break;

        }

Why not just use an if statement?

Edit: D'oh should have refreshed before I typed

Ok, I looked through the code this time...
1) As The Dark mentioned, using a while when you always break is kinda silly. That's what if statements are for.
2) Don't call main() from your own program.
3) Your if statement is incorrect. It's also pretty redundant (you already know n%2 is 0, so n%4, n%6, n%8, n%10 is pointless)

I took your code, sliced a lot out, and wrote my own version, if you'd like to compare. (I took out the system("pause") because it doesn't work on my computer :p) I didn't really comment it, but if you have questions, just ask

#include <iostream>
using namespace std;
 
bool isPrime(unsigned int n)
{
  if(!(n%2) || n < 9) // cover any n < 9; assumes 1 is prime
    return false;
  for(int i = 3; i*i <= n; i+=2)
  {
    if(!(n%i))
      return false;
  }
  return true;
}
 
void prime(int input)
{
  for (int n=10; n<=input; n++)
  {
    if(!(n%2))
    {
      cout << n << " is even" << endl;
      continue;
    }
    cout << n << " is odd ";
    if(isPrime(n))
      cout << "and prime";
    cout << endl;
  }
}
 
int main()
{
  int input = 0;
  while(true)
  {
    cout << "Enter number: ";
    cin >> input;
    if(input < 10)
      cout << endl << "Higher than 10 please..." << endl;
    else
      break;
  }
  prime(input);
}

Couple of comments on Jimbo's isPrime():
1. It assumes the input is an odd number. While it always true in this context when prime() calls it, a seperate call to isPrime(14) will return true instead of false because it is not checked for being a multiple of 2, and the loop will break before it reaches the other factor of 7.
2. In the n < 9 case, I think you meant to use "&&" instead of "||". And there needs to be a special case for when n is 2, because 2 is both even and prime.

While the isPrime() works perfectly when called by the current prime() function because the input is never even or less than 9, it would yield incorrect results if called by another function that didn't filter anything out first.

Here's an isPrime() that should work from any context:

bool isPrime(unsigned int n)
{
  if(n < 9) // cover any n < 9; assumes 1 is prime
    return n % 2 == 1 || n == 2; // true if odd or 2
  else if(n % 2 == 0) // quick check for evens
    return false;
 
  for(int i = 3; i*i <= n; i+=2)
  {
    if(!(n%i))
      return false;
  }
  return true;
}

I found this on some random site and it made me laugh:

Quote:

A mathematician, scientist, and engineer all set out to prove that all numbers are prime. The mathematician says "one is prime, two is prime, three is prime, they're all prime." The scientist says "one is prime, two is prime, three is prime, four is experimental error, five is prime, they're all prime." The engineer says "one is prime, two is prime, three is prime, four is prime, five is prime, they're all prime."

Its funny you should bring this up. Earlier today I made a similar program, though mine just goes through all numbers upto 1,000,000,000:

#include <iostream>
 
using namespace std;
 
int main() {
        int ind = 0;
        int prime;
        int max;
 
        int list[10000000] = {2};
 
        for (int i = 3;i < 1000000000;i++) {
 
                prime = 1;
 
                for (int j = 0; j < ind; j++) {
                        if ((i%list[j]) == 0) {
                                prime = 0;
                                break;
                        }
                }
 
                if (prime == 1) {
                        ind++;
                        list[ind] = i;
                        cout << i << "\n";
                }
        }
        return 0;
}

I had an earlier version that brute forced every number, but I found that only using primes works much faster.

._.

Guess I better hit the tutorial again.

edit:

Quote:

Originally Posted by Jimbo

2) Don't call main() from your own program.

I know that's probably not a good thing to do, but what else can I do? (Drawing a blank)

Quote:

Originally Posted by peaceofpi

._.
I know that's probably not a good thing to do, but what else can I do? (Drawing a blank)

A loop might be good...

I wrote this method for determining whether a number is prime a while ago. It is almost identical to the code posted by Kaja Fumei. I'm not sure if it completely correct though; if not I would appreciate any pointers.

bool is_prime(int x) {
    if (x % 2 == 0 || x == 1)
        return false;
    for (int i = 3; i <= sqrt(x); i += 2)
        if (x % i == 0)
            return false;
    return true;
}