Prime numbers

Question

Hi, I'm currently trying out some questions just to practice my programming skills. ( Not taking it in school or anything yet, self taught ) I came across this problem which required me to read in a number from a given txt file. This number would be N. Now i'm suppose to find the Nth prime number for N <= 10 000. After i find it i'm suppose to print it out to another txt file. Now for most parts of the question i'm able to understand and devise a method to get N. The problem is that I'm using an array to save previously found prime numbers so as to use them to check against future numbers. Even when my array was size 100, as long as the input integer was roughly < 15, the program crashes.

#include <cstdio>
#include <iostream>
#include <cstdlib>
#include <fstream>
using namespace std;

int main() {
    ifstream trial;
    trial.open("C:\\Users\\User\\Documents\\trial.txt");
    int prime;
    trial >> prime;
    ofstream write;
    write.open("C:\\Users\\User\\Documents\\answer.txt");
    int num[100], b, c, e;
    bool check;
    b = 0;
    switch (prime) {
        case 1:
        {
            write << 2 << endl;
            break;
        }
        case 2:
        {
            write << 3 << endl;
            break;
        }
        case 3:
        {
            write << 5 << endl;
            break;
        }
        case 4:
        {
            write << 7 << endl;
            break;
        }
        default:
        {
            for (int a = 10; a <= 1000000; a++) {
                check = false;
                if (((a % 2) != 0) && ((a % 3) != 0) && ((a % 5) != 0) && ((a % 7) != 0)) // first filter
                {
                    for (int d = 0; d <= b; d++) {
                        c = num[d];
                        if ((a % c) == 0) {
                            check = true; // second filter based on previous recorded primes in array
                            break;
                        }

                    }
                    if (!check) {
                        e = a;
                        if (b <= 100) {
                            num[b] = a;
                        }

                        b = b + 1;
                    }
                }
                if ((b) == (prime - 4)) {
                    write << e << endl;
                    break;
                }
            }
        }
    }
    trial.close();
    write.close();
    return 0;
}

I did this entirely base on my dummies guide and myself so do forgive some code inefficiency and general newbie-ness of my algorithm. Also for up to 15 it displays the prime numbers correctly.

Could anyone tell me how i should go about improving this current code? I'm thinking of using a txt file in place of the array. Is that possible? P.S I'm 15, so please go light on the heavy duty math =P

Answer 1

Since this is for pedagogical purposes, I would suggest implementing the Sieve of Eratosthenes.

Answer 2

I haven't looked at your code, but your array must be large enough to contain all the values you will store in it. 100 certainly isn't going to be enough for most input for this problem.

E.g. this code..

int someArray[100];
someArray[150] = 10;

Writes to a location large than the array (150 > 100). This is known as a memory overwrite. Depending on what happened to be at that memory location your program may crash immediately, later, or never at all.

A good practice when using arrays is to assert in someway that the element you are writing to is within the bounds of the array. Or use an array-type class that performs this checking.

For your problem the easiest approach would be to use the STL vector class. While you must add elements (vector::push_back()) you can later access elements using the array operator []. Vector will also give you the best iterative performance.

Here's some sample code of adding the numbers 0-100 to a vector and then printing them. Note in the second loop we use the count of items stored in the vector.

#include <vector> // std::vector

...

const int MAX_ITEMS = 100;

std::vector<int> intVector;

intVector.reserve(MAX_ITEMS); // allocates all memory up-front

// add items
for (int i = 0; i < MAX_ITEMS; i++)
{
  intVector.push_back(i);  // this is how you add a value to a vector;
}

// print them
for (int i = 0; i < intVector.size(); i++)
{
  int elem = intVector[i]; // this access the item at index 'i'
  printf("element %d is %d\n", i, elem);
}

Answer 3

There are a two approaches to testing for primality you might want to consider:

1. The problem domain is small enough that just looping over the numbers until you find the Nth prime would probably be an acceptable solution and take less than a few milliseconds to complete. There are a number of simple optimizations you can make to this approach for example you only need to test to see if it's divisible by 2 once and then you only have to check against the odd numbers and you only have to check numbers less than or equal to the aquare root of the number being tested.
2. The Sieve of Eratosthenes is very effective and easy to implement and incredibly light on the math end of things.

As for why you code is crashing I suspect changing the line that reads

for( int d=0; d<=b; d++)

to

for( int d=0; d<b; d++)

will fix the problem because you are trying to read from a potentially uninitialized element of the array which probably contains garbage.

Answer 4

For one, you'd have less code (which is always a good thing!) if you didn't have special cases for 3, 5 and 7.

Also, you can avoid the special case for 2 if you just set num[b] = 2 and only test for divisibility by things in your array.

Answer 5

It looks like as you go around the main for() loop, the value of b increases.

Then, this results in a crash because you access memory off the end of your array:

                for (int d = 0; d <= b; d++) {
                    c = num[d];

I think you need to get the algorithm clearer in your head and then approach the code again.

Answer 6

Running your code through a debugger, I've found that it crashes with a floating point exception at "if ((a % c) == 0)". The reason for this is that you haven't initialized anything in num, so you're doing "a % 0".

Answer 7

From what I know, in C/C++ int is a 16bit type so you cannot fit 1 million in it (limit is 2^16=32k). Try and declare "a" as long

I think the C standard says that int is at least as large as short and at most as large as long.

In practice int is 4 bytes, so it can hold numbers between -2^31 and 2^31-1.

Answer 8

Thanks for all the answers, I'll go edit the code now. For the sieve of eratosthenes can anyone explain how i would go about striking off or flagging the numbers that are nonprime/prime ?

Answer 9

This should also be of interest to you: http://en.wikipedia.org/wiki/Primality_test

Answer 10

Since your question is about programming rather than math, I will try to keep my answer that way too.

The first glance of your code makes me wonder what on earth you are doing here... If you read the answers, you will realize that some of them didn't bother to understand your code, and some just dump your code to a debugger and see what's going on. Is it that we are that impatient? Or is it simply that your code is too difficult to understand for a relatively easy problem?

To improve your code, try ask yourself some questions:

1. What are a, b, c, etc? Wouldn't it better to give more meaningful names?
2. What exactly is your algorithm? Can you write down a clearly written paragraph in English about what you are doing (in an exact way)? Can you modify the paragraph into a series of steps that you can mentally carry out on any input and can be sure that it is correct?
3. Are all steps necessary? Can we combine or even eliminate some of them?
4. What are the steps that are easy to express in English but require, say, more than 10 lines in C/C++?
5. Does your list of steps have any structures? Loops? Big (probably repeated) chunks that can be put as a single step with sub-steps?

After you have going through the questions, you will probably have a clearly laid out pseudo-code that solves the problem, which is easy to explain and understand. After that you can implement your pseudo-code in C/C++, or, in fact, any general purpose language.

Answer 11

I'm trying to improve my functional programming at the moment so I just coded up the sieve quickly. I figure I'll post it here. If you're still learning, you might find it interesting, too.

#include <iostream>
#include <list>
#include <math.h>
#include <functional>
#include <algorithm>

using namespace std;

class is_multiple : public binary_function<int, int, bool>
{
    public:
     bool operator()(int value, int test) const
     {
      if(value == test) // do not remove the first value
       return false;
      else
       return (value % test) == 0;
        }
};

int main() 
{
    list<int> numbersToTest;
    int input = 500;

    // add all numbers to list
    for(int x = 1; x < input; x++)
     numbersToTest.push_back(x);

    // starting at 2 go through the list and remove all multiples until you reach the squareroot
    // of the last element in the list
    for(list<int>::iterator itr = ++numbersToTest.begin(); *itr < sqrt((float) input); itr++)
    {
     int tmp = *itr;
     numbersToTest.remove_if(bind2nd(is_multiple(), *itr)); 
     itr = find(numbersToTest.begin(), numbersToTest.end(), tmp); //remove_if invalidates iterator 
                 // so find it again. kind of ugly
    }

    // output primes
    for(list<int>::iterator itr = numbersToTest.begin(); itr != --numbersToTest.end(); itr++)
     cout << *itr << "\t";

    system("PAUSE");

    return 0;
}

Any advice on how to improve this would be welcome by the way.

Answer 12

for(int currentInt=2; currentInt<=1000000; currentInt++) 

{check = false;  // Basically the idea for this for loop is to run checks against integers. This is the main for loop in this program. I re initialize check to false ( check is a bool declared above this. )

for( int arrayPrime=0; arrayPrime<currentPrime; arrayPrime++) // This for loop is used for checking the currentInt against previously found primes which are stored in the num array.

{ c=num[arrayPrime];
        if ((currentInt%c)==0) { check = true;// second filter based on previous recorded primes in array
                break;}  // this is the check. I check the number against every stored value in the num array. If it's divisible by any of them, then bool check is set to true.


if ( currentInt == 2)
{ check = false; } // since i preset num[0] = 2 i make an exception for the number 2.

if (!check)
{
e=a;
if(currentPrime <= 100){
num[currentPrime]= currentInt;} // This if uses check to see if the currentInt is a prime. 

currentPrime = currentPrime+1;} // increases the value of currentPrime ( previously b ) by one if !check.

if(currentPrime==prime)
{
write<<e<<endl;
break;}           // if currentPrime == prime then write the currentInt into a txt file and break loop, ending the program.

Thanks for the advice polythinker =)

Answer 13

#include <cstdio>
#include <iostream>
#include <cstdlib>
#include <fstream>

using namespace std;

int main()
{
ifstream trial;
trial.open("C:\\Users\\User\\Documents\\trial.txt");
int prime, e;
trial>>prime;
ofstream write; 
write.open("C:\\Users\\User\\Documents\\answer.txt");
int num[10000], currentPrime, c, primePrint;
bool check;
currentPrime=0;
num[currentPrime] = 2;
currentPrime=1;

for(int currentInt=2; currentInt<=1000000; currentInt++) 
{check = false; 
for( int arrayPrime=0; arrayPrime<currentPrime; arrayPrime++) 
        { c=num[arrayPrime];
            if ((currentInt%c)==0) { check = true;// second filter based on previous recorded primes in array
                    break;}
               }


 if (!check)
    { e=currentInt;  
    if( currentInt!= 2 ) { 
    num[currentPrime]= currentInt;}
    currentPrime = currentPrime+1;}
    if(currentPrime==prime)
    {
    write<<e<<endl;
    break;}
    }
trial.close();
write.close();
return 0;
}

This is the finalized version base on my original code. It works perfectly and if you want to increase the range of prime numbers simply increase the array number. Thanks for the help =)

Answer 14

Since you will need larger prime number values for later questions, I suggest you follow dreeves advice, and do a sieve. It is a very useful arrow to have in your quiver.