// I am having problems trrying to get my program run faster according to the chart where you run it. I need the program to run less than 10 seconds or even between 10 and 150 seconds for 500000

//This program finds all prime numbers greater than 1 and less than limit.

//(see variable limit below)

//Note that this particular version of the program is not very efficient.

//

//The instructor has written 5 versions, named "Slow" to "Fastest".

//Note that this program is the one called "Slow".

//The following table shows the time taken in seconds for each version

//for different limits.

//

// Limit

//Version 500,000 5,000,000 50,000,000

//------------------------------------------------

//Slow 251.00 too long too long

//Medium 153.00 too long too long

//Fast 1.00 20 498

//Faster 0.37 5 69

//Fastest 0.11 2 19

//

//The next table shows the number of primes found for different limits

//Use this table to make sure your program is producing the right number

//of primes

//

//Limit Number of Primes

//

//50,000,000 3,001,134

// 5,000,000 348,513

// 500,000 41,538

// 50,000 5,133

// 5,000 669

// 500 95

// 50 15

// 5 2

//Note that for limit 5, the program finds only 2 primes: 2 and 3.

//It does not find 5 because with a limit of 5, it only checks numbers 1-4.

#include <iostream>

#include <sys/timeb.h>

using namespace std;

//limit is the number of numbers to check for primeness

unsigned long int limit = 50000;

//This function checks to see if a number is prime

//It does this by dividing the number (number) by every smaller number (i)

//If the function finds an i that divides in evenly into number

//it returns false, otherwise it returns true

//Note that while this function does work, it is VERY slow.

bool isPrime( int x)

{

bool prime = (x > 1); //for numbers >= 2, init prime to true .

//for numbers < 2, init prime to false

// For loop runs as long as i is less than number and

// no i's have divided evenly into number (yet)

for (unsigned long int i=2; i < x / 2 + 1 && prime; x++)

{

//check for primeness by finding the remainder of number

//divided by i (number % i). The result is ANDED with prime.

//If the result is 0, prime becomes FALSE.

prime = prime && x % i;

if (i!= 2)

{

i++;

}

}

//return prime

return (prime);

}

//This function is a time keeping function

//Get the current "tick" count.

//Returns the number of "ticks" since 1/1/1970.

//A tick is 1/1000 of a second.

unsigned long int ticks()

{

unsigned long int tocks;

_timeb currTime; //create a variable of type _timeb

_ftime(&currTime); //get the current time

tocks = currTime.time; //currTime.time contains seconds since 1/1/1970

tocks *= 1000; //mulitply by 1000 to convert to ticks

tocks += currTime.millitm; //add in ticks

return tocks; //return # of 1/1000 seconds since 1/1/1970.

}

//main function

int main()

{

int x;

unsigned long int i, total, start, end;

//i is a counter variable

//total is used to count the number of primes found

//start is used to record the start time in 1/1000 of a second

//end is used to record the end time in 1/1000 of a second

//start time

start = ticks();

//init total to 0

total = 0;

//FOR LOOP

// init as long as add 1

// i to 1 i < limit to i

for (i=1; i<limit; i++)

{

x = (1 / 2)+ 1;

if (isPrime(i)) //check if i is prime

{

total++; //add one to total if number i is prime

}

}

//end time

end = ticks();

//display message

cout <<

"Program checked numbers from 1 to " << limit - 1 << endl <<

"It ran for " <<

(end-start) / 1000.0 <<

" seconds and found " <<

total <<

" prime numbers" <<

endl;

return 0;

}