Programming Forums > Projects > Show Off Your Open Source Projects

peaceofpi · Aug 30th, 2006, 7:34 PM

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

Jimbo · Aug 30th, 2006, 7:52 PM

Try using 121 for your input

The Dark · Aug 30th, 2006, 7:54 PM

121 doesn't work

Also, this code seems odd:

(Toggle Plain Text)

        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

Jimbo · Aug 30th, 2006, 8:08 PM

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

 cpp Syntax (Toggle Plain Text) 
#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);
}
#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);
}

Kaja Fumei · Aug 30th, 2006, 9:25 PM

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:

 cpp Syntax (Toggle Plain Text) 
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;
}
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;
}

titaniumdecoy · Aug 30th, 2006, 9:33 PM

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."

glimmy · Aug 30th, 2006, 9:48 PM

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:

 cpp Syntax (Toggle Plain Text) 
#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;
}
#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.

peaceofpi · Aug 30th, 2006, 9:55 PM

._.

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)

glimmy · Aug 30th, 2006, 10:12 PM

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...

titaniumdecoy · Aug 30th, 2006, 10:13 PM

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.

 cpp Syntax (Toggle Plain Text) 
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;
}
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;
}

Aug 30th, 2006, 7:34 PM	#1
peaceofpi hi: for(;;) goto hi; Join Date: Jun 2006 Posts: 94 Rep Power: 3	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 __________________ How do you play Religious Roulette? Stand around in a circle and blaspheme till someone gets struck by lightning.

Aug 30th, 2006, 7:54 PM	#3
The Dark Expert Programmer Join Date: Jun 2005 Posts: 852 Rep Power: 4	121 doesn't work Also, this code seems odd: (Toggle Plain Text) 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; } 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

Aug 30th, 2006, 8:08 PM	#4
Jimbo Battle Programmer Join Date: Feb 2006 Location: Bellevue, WA, USA Posts: 763 Rep Power: 3	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 cpp Syntax (Toggle Plain Text) #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; ii <= 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); } #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; ii <= 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); }

Aug 30th, 2006, 9:25 PM	#5
Kaja Fumei Hobbyist Programmer Join Date: Oct 2005 Posts: 134 Rep Power: 3	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: cpp Syntax (Toggle Plain Text) 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; ii <= n; i+=2) { if(!(n%i)) return false; } return true; } 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; ii <= n; i+=2) { if(!(n%i)) return false; } return true; }

Aug 30th, 2006, 9:48 PM	#7
glimmy Programmer Join Date: May 2005 Location: Minnesota Posts: 42 Rep Power: 0	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: cpp Syntax (Toggle Plain Text) #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; } #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.

Aug 30th, 2006, 7:52 PM	#2
Jimbo Battle Programmer Join Date: Feb 2006 Location: Bellevue, WA, USA Posts: 763 Rep Power: 3	Try using 121 for your input

Aug 30th, 2006, 10:13 PM	#10
titaniumdecoy Expert Programmer Join Date: Nov 2005 Posts: 856 Rep Power: 3	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. cpp Syntax (Toggle Plain Text) 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; } 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; }

Currently Active Users Viewing This Thread: 1 (0 members and 1 guests)

Thread Tools
Show Printable Version Email this Page
Display Modes
Switch to Linear Mode Hybrid Mode Switch to Threaded Mode

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
Median/Mode in arrays? {Need help}	Java\|Tera	Java	27	Nov 29th, 2005 10:50 AM
Prime Numbers	Konnor	C++	6	Sep 12th, 2005 6:46 PM
Generating prime and composite numbers	saadmir	C	5	Sep 9th, 2005 4:08 PM
Prime numbers	thomzor	C++	24	May 20th, 2005 2:02 PM
Help with a couple prime numbers programs!!	BehemothPhoenix	C++	3	Mar 20th, 2005 2:06 PM

Programming Forums > Projects > Show Off Your Open Source Projects

Calculate prime numbers