Prime Program

[Schmidt1989]

This is a homework assignment yet i am just completely lost, any help is greatly appreciated. This is what ive got so far:


#include <iostream>
#include <math.h>

using namespace std;

int main()
{
const int length=50;
int list[length]={1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,
16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,
34,35,36,37,38,39,40,41,42,43,44,45,46,47,48,49,50};
int rerun;
int number;

do
{
cout << "Enter a number to see if its prime: ";
cin >> number;

while(number <1 || number > 50){
cout << "Please enter a new number between 1 and 50: ";
cin >> number;

}

if (number == 1)
{
cout << "The number 1 is a unit, it is neither prime nor composite"<<endl;
}

if (number==2 || number==3 || number==5 || number==7)
{
cout <<"Prime"<<endl;
}
else
if (number %2 !=0 || number %3 !=0 || number %5 !=0 || number %7 !=0)
{
cout << "composite"<<endl;
}
else
if (number /2 || number /3 || number /5 || number /7)
{
cout << "Composite"<<endl;
}
cout << "Enter any number to continue or 0 to quit: ";
cin >> rerun;

}while (rerun !=0);

return 0;
}

[Spookster]

It would be easier to help you if you had a specific question. What is it your having trouble with?

[Schmidt1989]

if i enter 1, it says neither composite nor prime then below it says composite, and then numbers 10-20 are all displayed as composite.

[Spookster]

Hmmm. I am guessing your assignment was probably to write a program that takes a number from the user and then determines if the number was prime or composite?

If that is the case the key here is to come up with an algorithm first before writing any code.

A prime number is a number that only divides evenly by 1 and itself. With that in mind how can you determine if a number is prime?

You really don't need that array of integers nor do you need that do while loop. Think about the problem first.

Programmatically how can you determine if a number divides evenly only by 1 and itself?

The gist of your program is going to be:

number = input from user

determine if number divides evenly by only 1 and itself.

If it does then it is prime

Else it is composite.

[jkd]

You really don't need that array of integers nor do you need that do while loop. Think about the problem first.

A sieving algorithm would require the array, actually. And sieving algorithms are typically superior to direct-search algorithms for finding prime numbers.

So Spook said that a prime number is divisible by one and itself. So given n, 2 can't divide, 3 can't divide, 4 can't divide, ..., n-1 can't divide. The algorithm practically writes itself. There are several important optimizations one should make though, which you're left as a student to figure out.

[Spookster]

A sieving algorithm would require the array, actually. And sieving algorithms are typically superior to direct-search algorithms for finding prime numbers.


:p I was thinking in terms of what an instructor would expect for an intro to programming course.

[bcarl314]

Actually, the best seive would be to only check for prime divisors upto the square root of the number. Anything else would be redundant checks.

For example:

If you want to check if 473 is prime, you would only need to check the prime numbers up to 21 (e.g. 2,3,5,7,11,13,17,19)

I can't remember what this seive is called, but it's one of the most effient method for determining prime numbers.

[jkd]

Actually, the best seive would be to only check for prime divisors upto the square root of the number. Anything else would be redundant checks.

Was trying to leave it a challenge for the student. There are numerous optimizations to be made.

Sieve of Eratosthenes, by the way.