Prime Numbers List

[SkarFaceT9]

I'm having trouble with this program trying to write prime numbers to a txt file.
I just get a long list of -2147483647

#include <iostream>
#include <iomanip>
#include <fstream>
using namespace std;

void isPrime(int);

int main()
{
int number = 2;
cout << "This program will store all number from 1 to 1000 to a text file." << endl;

isPrime(number);

system("pause");
return 0;
}

void isPrime(int i)
{
int number = 3;
ofstream Prime_Numbers;
Prime_Numbers.open("Prime_Numbers.txt");
while (number <= 999)
{
while (number > i)
{
if (number % i == 0)
{
i += 2;
}
number += 2;
i = 2;
}
Prime_Numbers << number << endl;
}
Prime_Numbers.close();
}

[Boxbird]

#include <iostream>
#include <iomanip>
#include <fstream>
using namespace std;

bool isPrime(int);

int main()
{
	int i;
	ofstream outFile("Prime_Numbers.txt");
	cout << "This program will store all number from 2 to 1000 to a text file." << endl;

	for(i = 2; i <= 1000; i++)
		if(isPrime(i)) outFile << i << endl;

	outFile.close();
	system("pause");
	return 0;
}

bool isPrime(int i)
{
	int nFactors = 0;
	for(int k = 1; k <= i; k++) if(i % k == 0) nFactors++;

	return (nFactors == 2);
}

[lastchance]

Boxbird:
- if you are only deciding whether a number is prime then you don't need to count its factors: you can return as soon as you have found a factor other than 1; for large numbers this is a substantial saving in operations;
- you don't need to start from k=1; that is always a factor and isn't a criterion for primeness;
- and you don't need to test beyond sqrt(i); if you haven't found a factor (other than 1 and i) by then, you won't be finding any others.

Also, if you are only searching up to n=1000 you may find it easier to use the Sieve of Eratosthenes (striking out multiples and seeing what's left) rather than testing every number for its factors.

[Boxbird]

@lastchance
Well, thanks for your suggestion.

#include <iostream>
#include <iomanip>
#include <fstream>
using namespace std;

bool isPrime(int);

int main()
{
	int i;
	ofstream outFile("Prime_Numbers.txt");
	cout << "This program will store all number from 2 to 1000 to a text file." << endl;

	for(i = 2; i <= 1000; i++)
		if(isPrime(i)) outFile << i << endl;

	outFile.close();
	system("pause");
	return 0;
}

bool isPrime(int i)
{
	for(int k = 2; k < i; k++) if(i % k == 0) return false; return true;
}

Is it correct?

[lastchance]

It's correct but you don't need to search as far as i in isPrime(); if any non-trivial factors exist then one factor at least must be smaller than the square root of i, so you don't need to search any further than that.

You also should have header
#include<cstdlib>
in order to use system()

Try to help the original poster to learn, rather than immediately giving him code.

[Boxbird]

I have figured out a quicker way to make the function isPrime() faster. Not sure if it is actually correct.

#include <iostream>
#include <iomanip>
#include <fstream>
using namespace std;

bool isPrime(int);

int main()
{
	int i;
	ofstream outFile("Prime_Numbers.txt");
	cout << "This program will store all number from 2 to 1000 to a text file." << endl;

	for(i = 2; i <= 1000; i++)
		if(isPrime(i)) outFile << i << endl;

	outFile.close();
	system("pause");
	return 0;
}

bool isPrime(int i)
{
	for(int k = 2; k <= (i / 2); k++) if(i % k == 0) return false; return true;
}

Is it the right thing to do?

[lastchance]

You still shouldn't need to search beyond sqrt(i). That is usually much smaller than i/2. Try it!
You will need header
#include<cmath>
to use it.

And a sieve-based method will still be faster ...

[Boxbird]

lastchance wrote:

You still shouldn't need to search beyond sqrt(i). That is usually much smaller than i/2. Try it!

What if the number is divisible by 2? I can't comprehend this...

For example, 64. sqrt(64) is 8, and 64 is divisible by 2 and 32. Sorry I can't follow...

[Boxbird]

lastchance wrote:

And a sieve-based method will still be faster...

http://www.sanfoundry.com/cpp-program-implement-sieve-eratosthenes/
That requires an array to do it... It is really not suitable for checking very large numbers to see whether they are prime numbers or not. And it is more complex.

[lastchance]

What if the number is divisible by 2? I can't comprehend this...

For example, 64. sqrt(64) is 8, and 64 is divisible by 2 and 32. Sorry I can't follow... 

So you are checking whether 64 has ANY factors (other than 1 and 64)
Yes, you find that 64 = 2 x 32.
I think you will find that 2 is less than sqrt(64)=8. By the time you get to 8 you will have found out whether 64 is prime or not. You do NOT need to go as far as 64/2=32 to decide whether it is prime.

If
x times y = N
then ONE OF x or y must be less than or equal to sqrt(N).

[1vRz3TCk]

Boxbird wrote:

What if the number is divisible by 2? I can't comprehend this...

With your number (n) having two factors (a and b) then n= a*b.

The largest that both a and b can be at the same time can not be more than the square root of n. Therefore one of the factors must always be less than or equal to the square root of n.

[Boxbird]

lastchance wrote:

You still shouldn't need to search beyond sqrt(i). That is usually much smaller than i/2. Try it!

To tell the truth, I still don't fully comprehend this, however it should be worth giving it a shot since this may look like an idiom and it appears to be pretty practical and popular.

#include <iostream>
#include <iomanip>
#include <fstream>
#include <cmath>
#include <cstdlib>
using namespace std;

bool isPrime(int);

int main()
{
	int i;
	ofstream outFile("Prime_Numbers.txt");
	cout << "This program will store all number from 2 to 1000 to a text file." << endl;

	for(i = 2; i <= 1000; i++)
		if(isPrime(i)) outFile << i << endl;

	outFile.close();
	system("pause");
	return 0;
}

bool isPrime(int i)
{
	int k, N;
	if(i <= 1) return false; else N = sqrt(i);
	for(k = 2; k <= N; k++) if(i % k == 0) return false; return true;
}

lastchance wrote:

Yes, you find that 64 = 2 x 32.
I think you will find that 2 is less than sqrt(64)=8. By the time you get to 8 you will have found out whether 64 is prime or not. You do NOT need to go as far as 64/2=32 to decide whether it is prime.

CodeMonkey wrote:

With your number (n) having two factors (a and b) then n= a*b.

The largest that both a and b can be at the same time can not be more than the square root of n. Therefore one of the factors must always be less than or equal to the square root of n.

I understand it now. Thank you both very much!

[Arslan7041]

That requires an array to do it... It is really not suitable for checking very large numbers to see whether they are prime numbers or not. And it is more complex.

He is right. A sieve algorithm would be faster in this case, and more intuitive.

[lastchance]

And here's my take on the Sieve of Eratosthenes. Sure, it needs an array, but it has only one floating point multiply or divide (which I could have chosen to avoid if I wished), so it should be fast.

It's not that complex - it's taught to British primary school kids.

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

int main()
{
   int nmax = 1000;                                        // maximum number
   int i;
   int start, test;

   bool *crossedOff = new bool[nmax+1];                    // ignores the [0] element for convenience
   crossedOff[1] = true;                                   // 1 isn't prime
   for ( i = 2; i <= nmax; i++ ) crossedOff[i] = false;    // rest are potential multiples

   // For each number 'start' less than or equal to nmax / 2 (and not already crossed off) cross off if its multiples (i.e. 2 or more times)
   for ( start = 1; start <= ( nmax + 1 ) / 2; start++ )
   {
      if ( crossedOff[start] ) continue;                   // multiples already crossed off; don't bother

      test = start + start;
      while ( test <= nmax )
      {
         crossedOff[test] = true;
         test += start;
      }
   }


   // Write everything left to file
   ofstream out( "file.txt" );
   for ( i = 1; i <= nmax; i++ )
   {
      if ( !crossedOff[i] ) out << i << endl;
   }
   out.close();
}

[1vRz3TCk]

That^{[sieve-based]} requires an array to do it... It is really not suitable for checking very large numbers to see whether they are prime numbers or not. And it is more complex.

For this type of list generation a sieve should be better

#include <iostream>

/******************************************************************************
The sieve of Eratosthenes to determine prime numbers
The algorithm
1 Create a contiguous list of numbers from two to some integer n.
2 Strike out from the list all multiples of two (4, 6, 8 etc.).
3 The list's next number that has not been struck out is a prime number.
4 Strike out from the list all multiples of the number you identified in the 
  previous step.
5 Repeat steps 3 and 4 until you reach n.
******************************************************************************/
long sieve(long n, long* primes) 
{
    if (n<2) return 0; 
    
    const char blank = 0;
    const char marked = 1;

    char* theSieve;

    theSieve = new char[n+1];
    
    for (long k=2; k<=n; k++) 
        theSieve[k] = blank;

    long idx = 0;
  
    for (long k=2; k<=n; k++) 
    {
        if (theSieve[k]==blank) 
        {
            theSieve[k] = marked;
            primes[idx] = k;
            idx++;

            for(long d=2*k; d<=n; d+=k) 
                theSieve[d] = marked;
        }
    }
    delete[] theSieve;
    return idx;
}

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

const long N = 10000000;
const long TABLE_SIZE = 800000;

int main() 
{
    long* primes; 
    primes = new long[TABLE_SIZE];
    long np = sieve(N,primes);

    std::cout << "Found " << np << " prime numbers" << std::endl;
    std::cout << "The largest prime number is " << primes[np-1] << std::endl;

    delete[] primes;

    return 0;
}

[Boxbird]

I did a quick benchmark and found that the "Sieve of Eratosthenes" is significantly faster, despite it being long and more complex. I will be using this algorithm from now on, even I can't absorb it right away but soon enough.

#include <iostream>
#include <fstream>
#include <cmath>
#include <ctime>

using namespace std;

void writePrimeArray()
{
   int nmax = 999999;                                        // maximum number
   int i;
   int start, test;

   bool *crossedOff = new bool[nmax+1];                    // ignores the [0] element for convenience
   crossedOff[1] = true;                                   // 1 isn't prime
   for (i = 2; i <= nmax; i++) crossedOff[i] = false;    // rest are potential multiples

   // For each number 'start' less than or equal to nmax / 2 (and not already crossed off) cross off if its multiples (i.e. 2 or more times)
   for (start = 1; start <= ( nmax + 1 ) / 2; start++)
   {
      if (crossedOff[start]) continue;                   // multiples already crossed off; don't bother

      test = start + start;
      while (test <= nmax)
      {
         crossedOff[test] = true;
         test += start;
      }
   }

   // Write everything left to file
   ofstream out("file.txt");
   for (i = 1; i <= nmax; i++)
   {
      if (!crossedOff[i]) out << i << endl;
   }
   out.close();
   delete [] crossedOff; // lastchance's fix
}

bool isPrime(int i)
{
	int k, N;
	if(i <= 1) return false; else N = sqrt(i);
	for(k = 2; k <= N; k++) if(i % k == 0) return false; return true;
}

void writePrimeNormal()
{
	int i;
	int nmax = 999999;     
	ofstream out("file2.txt"); 
	for(i = 0; i < nmax; i++) if(isPrime(i)) out << i << endl;
	out.close();
}

int main()
{
	clock_t start_t, end_t;

	start_t = clock();
	writePrimeArray();
	end_t = clock();

	cout << "Sieve of Eratosthenes time elapsed : " << (double)(end_t - start_t) / (double) CLOCKS_PER_SEC << endl;

	start_t = clock();
	writePrimeNormal();
	end_t = clock();

	cout << "Normal algorithm time elapsed : " << (double)(end_t - start_t) / (double) CLOCKS_PER_SEC << endl;

	return 0;
}

Sieve of Eratosthenes time elapsed : 0.453
Normal algorithm time elapsed : 0.766

Edit :
@lastchance
You forgot to delete the dynamic array when everything is done.