Prime Number Code

[cmog]

I am fairly new to C++ and I am trying to write a code that determines whether a number which the user inputs is prime or not. I have the code, but when I run it all it actually does is report odd numbers as prime and even numbers as not prime. Can anybody help me out and see what the problem might be? Thanks in advance.

#include <iostream>
using namespace std;
//declaring variables//
int i;
int num;

int main()
{
    //asking for a number, and hardcoding that 1 and 2 are prime//
  cout<<"Input a number"<<endl;
  cin>>num;
if (num==1)
{
    cout<<num<<" is prime."<<endl;
}
if (num==2)
{
    cout<<num<<" is prime."<<endl;
}
//for-loop so the number is divided by 1 through itself//
  for (i=1;i<=num;i++)
{

//saying that if the number is divisible by i when i is not equal to 1 or itself then it is not prime, otherwise it is.//
  while (i>1&&i<num)
  {
    if (num%i==0)
    {
        cout<<num<<" is not prime."<<endl;
    }
    else {cout<<num<<" is prime."<<endl;}
    return 0;
  }
}
}

[poteto]

int p[500] = { 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 
            73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173,
            179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281,
            283, 293, 307, 311, 313, 317, 331, 337, 347, 349, 353, 359, 367, 373, 379, 383, 389, 397, 401, 409,
            419, 421, 431, 433, 439, 443, 449, 457, 461, 463, 467, 479, 487, 491, 499, 503, 509, 521, 523, 541,
            547, 557, 563, 569, 571, 577, 587, 593, 599, 601, 607, 613, 617, 619, 631, 641, 643, 647, 653, 659,
            661, 673, 677, 683, 691, 701, 709, 719, 727, 733, 739, 743, 751, 757, 761, 769, 773, 787, 797, 809,
            811, 821, 823, 827, 829, 839, 853, 857, 859, 863, 877, 881, 883, 887, 907, 911, 919, 929, 937, 941,
            947, 953, 967, 971, 977, 983, 991, 997, 1009, 1013, 1019, 1021, 1031, 1033, 1039, 1049, 1051, 1061, 1063, 1069,
            1087, 1091, 1093, 1097, 1103, 1109, 1117, 1123, 1129, 1151, 1153, 1163, 1171, 1181, 1187, 1193, 1201, 1213, 1217, 1223,
            1229, 1231, 1237, 1249, 1259, 1277, 1279, 1283, 1289, 1291, 1297, 1301, 1303, 1307, 1319, 1321, 1327, 1361, 1367, 1373,
            1381, 1399, 1409, 1423, 1427, 1429, 1433, 1439, 1447, 1451, 1453, 1459, 1471, 1481, 1483, 1487, 1489, 1493, 1499, 1511,
            1523, 1531, 1543, 1549, 1553, 1559, 1567, 1571, 1579, 1583, 1597, 1601, 1607, 1609, 1613, 1619, 1621, 1627, 1637, 1657,
            1663, 1667, 1669, 1693, 1697, 1699, 1709, 1721, 1723, 1733, 1741, 1747, 1753, 1759, 1777, 1783, 1787, 1789, 1801, 1811,
            1823, 1831, 1847, 1861, 1867, 1871, 1873, 1877, 1879, 1889, 1901, 1907, 1913, 1931, 1933, 1949, 1951, 1973, 1979, 1987,
            1993, 1997, 1999, 2003, 2011, 2017, 2027, 2029, 2039, 2053, 2063, 2069, 2081, 2083, 2087, 2089, 2099, 2111, 2113, 2129,
            2131, 2137, 2141, 2143, 2153, 2161, 2179, 2203, 2207, 2213, 2221, 2237, 2239, 2243, 2251, 2267, 2269, 2273, 2281, 2287,
            2293, 2297, 2309, 2311, 2333, 2339, 2341, 2347, 2351, 2357, 2371, 2377, 2381, 2383, 2389, 2393, 2399, 2411, 2417, 2423,
            2437, 2441, 2447, 2459, 2467, 2473, 2477, 2503, 2521, 2531, 2539, 2543, 2549, 2551, 2557, 2579, 2591, 2593, 2609, 2617,
            2621, 2633, 2647, 2657, 2659, 2663, 2671, 2677, 2683, 2687, 2689, 2693, 2699, 2707, 2711, 2713, 2719, 2729, 2731, 2741,
            2749, 2753, 2767, 2777, 2789, 2791, 2797, 2801, 2803, 2819, 2833, 2837, 2843, 2851, 2857, 2861, 2879, 2887, 2897, 2903,
            2909, 2917, 2927, 2939, 2953, 2957, 2963, 2969, 2971, 2999, 3001, 3011, 3019, 3023, 3037, 3041, 3049, 3061, 3067, 3079,
            3083, 3089, 3109, 3119, 3121, 3137, 3163, 3167, 3169, 3181, 3187, 3191, 3203, 3209, 3217, 3221, 3229, 3251, 3253, 3257,
            3259, 3271, 3299, 3301, 3307, 3313, 3319, 3323, 3329, 3331, 3343, 3347, 3359, 3361, 3371, 3373, 3389, 3391, 3407, 3413,
            3433, 3449, 3457, 3461, 3463, 3467, 3469, 3491, 3499, 3511, 3517, 3527, 3529, 3533, 3539, 3541, 3547, 3557, 3559, 3571};

I would just loop through it till the value is equal or less than the value.

[TheIdeasMan]

Hi,

Welcome to cplusplus :+)

I think your main problem is you need some more variables. The i and num on line 25 are the same ones as on line 21. You a different variable so as to not disturb the for loop.

Also, you could improve this by only checking up to a limit of sqrt(num).

And, your loop should continue or restart once a non prime is discovered.

Btw, some more meaningful variable names would be good. num is not such a good name.

I know you are a beginner, and this is seemingly a beginner problem, but I thought I would point out some stuff that would make you think a bit :+) Note that all this is way beyond what you might be reasonably expected to do in your assignment.

I just wrote some prime number code recently, and took a very different approach to yours.

For my problem I had to work out ALL the primes up to 2 million !

So your algorithm wouldn't work as well (if it were used to work all primes, rather than 1 prime), because:

- it is very very inefficient, when the number is prime, because it tests all the numbers, so if we only wanted to work out the last 5 before 2 million, then the code would loop just short of 10 million times! This includes testing all the even numbers as well, which is a waste.

- if the sqrt of the number is prime, it loops through all those numbers up to that value.

- The execution time of your program would increase somewhat less than factorial(n). Because the execution time is very long, it could only be used for very small values of n.

So I did this:

I put all the odd numbers from 3 onwards into a container. The CurrentNumber is now 3.

Edit: this part causes problems
Next, I remove all the powers of the CurrentNumber less than the Limit. At this stage 3² 3³ 3⁴..... etc

Then, I remove all the multiples of the CurrentNumber where the other factor is the other numbers in the container greater than the CurrentNumber. That is, at this stage, 3*5, 3*7, 3*9, 3*11, 3*13 etc up to the multiple is less than Limit. Note, we are not testing all the numbers left in the container to see if it a multiple of CurrentNumber, because we don't want to test anything that is less than CurrentNumber distance apart.

Then, follow the same procedure using the next number in the container after the current one.

So I did a bit of work writing the code to do that, but it has several advantages.

To start with, I had almost 1 million numbers in the container, but this gets shorter very quickly. My program executes in about 0.5 seconds.

It is quicker to work out all the primes, then use some find function to see whether a number is prime or not, rather than an inefficient function to see if the number is prime.

I hope this has provided a bit of insight, and might be useful to you in the future.

Cheers

[TheIdeasMan]

Hi again,

Here is something you might be able to implement yourself.

A much simpler, but slightly less efficient algorithm for doing this:

Start with a list of all the numbers up to Limit

1 is a special number so we ignore that.

The next value in the list is 2, so we remove all multiples of it from the list. I short cut this by only creating odd numbers in the first place.

Now, the next value is 3, so we remove all multiples of it.

Move to the next value in the list and remove multiples of it.


Doing it this way means that: any number > n which has factors < n, will not be in the list.

It less efficient than the method in my previous post because it tests too many numbers. For example it tests whether 23 is a multiple of 19, which is unnecessary.

[mynicks]

the solution to your problems. It works.Make sure you understand what it does because icopy pasted from elsewhere and modified it( i placed it inside a function testprime).. The secret is hidden in part:
for(int i=2; i*i<=a; i++) where i also do not fully comprehend.

#include <iostream>
#include <stdlib.h>

using namespace std;
bool testprime(int a)
{
    if(!a)
        return false;
    else
    {
        for(int i=2; i*i<=a; i++)
        {
            if(a%i==0)
            return false;
        }
        return true;
    }
}
int main(int argc, char *argv[])
{
    int a;
    bool b;
    cout << "prime number test. Enter number: ";
    cin >> a;
    b=testprime(a);
    if (!(b==0))
        cout << a << " is a prime number.\n";
    else
        cout << a << " is not a prime number.\n";
    cout <<"\n\n";
    //system("pause"); many people hate this code line :P
}

[TheIdeasMan]

@mynicks

Congratulations, you just completed the OP's homework. Although he/she might have found it on the net anyway, so you even saved that effort.

It is better to give the OP hints on how to do things.

[mynicks]

@TheIdeasMan

Oh really? I'm sorry if that upsets you.

btw my version of the code is heavily modified to the original one to suit my needs. Only the for(int i=2; i*i<=a; i++) and if(a%i==0) are the same as the original code. I do not really mind if he/she copy paste it and give it to his/her professor/employer.
Plus, my code has a trap.... A good professor will find it :D I just gave away a really good percentage of my implementation. It is a true help for someone rather than dropping hints...

The idea is simple and maybe naive: offer genuine Help to get helped.
When i can i will help with spot on examples and i expect to receive true help by others who are good at programming.

[cmog]

Wow thanks for all the feedback guys, I guess I still have a lot of work to do.