# Prime

A little program I made to try and remeber C++, first program I've written in C++ in about a year.

Tested and working under windows 7 64 bit, run via command line.

Cheers K0ns3rv

``````/*
* File:   main.cpp
* Author: K0ns3rv
* Email: info@k0nserv.se
* Description: Utility tool when working with prime numbers
* Created on den 11 juni 2010, 19:12
*
* Usage: Use, modify and distribute as you wish. I do like credit :)
*/

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

/*
* Checks if a given number is a prime number e.g only evenly divisible by itself and 1
*/
bool isPrime (int n) {
for ( int i = 2; i < n; i++ ) {
if ( n % i == 0 ) {
return false;
}
}
return true;
}

/*
* Display the command syntax
*/
void displayOptions () {
std::cout << "Invalid arguments " << std::endl;
std::cout << "The following arguments are valid " << std::endl;
std::cout << "-s Finds all numbers in the range 0 to second argument. Usage -s [max] [output] [filepath]" << std::endl;
std::cout << "-f Factorize a given number, the second argument, as prime numbers. Usage -f [number]" << std::endl;
std::cout << "-r Find all numbers in range first  argument to second argument. Usage -r [min] [max] [output] [filepath]" << std::endl;
std::cout << "-c Check if given number is a prime. Usage -c [number]" << std::endl;
}

/*
* Find all prime numbers in the the interval lowerRange to range
* outputNumbers will ,if true, write the found primes the console.
* OutputPath will, if defined, write the numbers to a file
* array will, if true, return the numbers as an std::vector<int>
*/
std::vector<int> find (int range, bool outputNumbers, char* outputPath = NULL, bool array = false, int lowerRange = 2) {
std::vector<int> primes;
int startPos; //Starting position in the input file
bool fileOutput = true;
ofstream file;

if ( !array ) {
std::cout << "Min: " << lowerRange << std::endl;
std::cout << "Max: " << range << std::endl;
}

if ( outputPath != NULL ) {
std::cout << "Selected output path: " << outputPath << std::endl;
}

else {
fileOutput = false;
}

std::cout << "Running... \n" << std::endl;
if ( fileOutput ) {
file.open ( outputPath, ios::app );
startPos = file.tellp ( );
}

for ( int i = lowerRange; i < range; i++ ) {
if ( isPrime ( i ) ) {
if ( array ) {
primes.push_back ( i );
}

if ( outputNumbers ) {
std::cout << i << std::endl;
}

if ( fileOutput ) {

file << i;
if ( i + 1 < range ) {
file << ",";
}
file << "\r\n";
}
}
}
if ( fileOutput ) {
std::cout << "Wrote " << (int) file.tellp ( ) - startPos << " bytes to " << outputPath << std::endl;
file.close ( );
}
return primes;
}

/*
* Factorize a given number in primes e.g 6 = 3 * 2 and 25 = 5^2
*/
void factorize (int value) {
bool running = true;
std::vector<int> primes = find ( value, false, NULL, true );
std::vector<int> result;

while ( running ) {
//std::cout << "value: " << value << std::endl;
if ( isPrime ( value ) ) {
result.push_back ( value );
running = false;
break;
}

for ( int loc = 0; loc < primes.size ( ); loc++ ) {
if ( value % primes.at ( loc ) == 0 ) {
//std::cout << "Divided by : " << primes.at(loc) << std::endl;
result.push_back ( primes.at ( loc ) );
value = value / primes.at ( loc );
break;
}
}
}
std::cout << "Result: ";
int numericResult = 1;
for ( int loc = 0; loc < result.size ( ); loc++ ) {
std::cout << result.at ( loc );

if ( !(result.back ( ) == result.at ( loc )) ) {
std::cout << " * ";
}
numericResult *= result.at ( loc );
}
std::cout << " = " << numericResult << std::endl;
}

/*
* Check if a given number is a prime number
*/
void checkPrime (int c) {
if ( isPrime ( c ) ) {
std::cout << c << " is a prime number" << std::endl;
}
else {
char* check;
std::cout << c << " is not a prime number, run \"-f " << c << "\" to find out what prime numbers is it's factors" << std::endl;
std::cout << "Would you like to do that now ? (Y/N): ";
std::cin >> check;
if ( !strcmp ( check, "Y\0" ) || !strcmp ( check, "y\0" ) ) {
factorize ( c );
}
}
}

int main (int argc, char** argv) {
if ( argc < 3 ) {//Invalid amount of arguments
displayOptions ( );
return 0;
}
else {
if ( !strcmp ( argv[1], "-f\0" ) || !strcmp ( argv[1], "-F\0" ) ) {//Factorize
factorize ( atoi ( argv[2] ) );
}

else if ( (!strcmp ( argv[1], "-s\0" ) || !strcmp ( argv[1], "-S\0" )) && argc > 3 ) {//search
if ( argc == 5 ) {
find ( atoi ( argv[2] ), !strcmp ( argv[3], "true\0" ), argv[4] );
}
else if ( argc == 4 ) {
find ( atoi ( argv[2] ), !strcmp ( argv[3], "true\0" ) );
}
else {
displayOptions ( );
}
}
else if ( (!strcmp ( argv[1], "-r\0" ) || !strcmp ( argv[1], "-R\0" )) && argc > 4 ) {//Search with min and max
if ( argc == 6 ) {
find ( atoi ( argv[3] ), !strcmp ( argv[4], "true\0" ), argv[5], false, atoi ( argv[2] ) );
}
else if ( argc == 5 ) {
find ( atoi ( argv[3] ), !strcmp ( argv[4], "true\0" ), NULL, false, atoi ( argv[2] ) );
}
else {
displayOptions ( );
}
}
else if ( (!strcmp ( argv[1], "-c\0" ) || !strcmp ( argv[1], "-c\0" )) ) {//check prime
checkPrime ( atoi ( argv[2] ) );
}

else {
displayOptions ( );
return 0;
}
}
return (EXIT_SUCCESS);
}``````

When testing prime-ness (prim-ity? prime-nitude?) in
the function isPrime(), you don't need to go all the way to n.
You only need to conduct this search up to sqrt(n), i.e.

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

If there is a number y, that divides n, and y > sqrt(n),
then there has to be another number z, z < sqrt(n), such
that `z * y= n`. So if you already know that no number below
sqrt(n) divides n, you are done.

Ah that's great thanks, didn't think of that :)

On another note I am confused by the deprecated headers.
I can compile the program with the following includes

``````#include <iostream>
#include <fstream.h>
#include <vector.h>
#include <cmath>``````

But I of course still get the warning

/usr/lib/gcc/i686-pc-cygwin/3.4.4/include/c++/backward/backward_warning.h:32:2: warning: #warning This file includes at least one deprecated or antiquated header. Please consider using one of the 32 headers found in section 17.4.1.2 of the C++ standard. Examples include substituting the <X> header for the <X.h> header for C++ includes, or <iostream> instead of the deprecated header <iostream.h>. To disable this warning use -Wno-deprecated.

I checked 17.4.1.2 of the C++ standard and found that the following include should be correct

``````#include <iostream>
#include <fstream>
#include <vector>
#include <cmath>``````

It isn't, the compiler is not able to locate the ofstream object an a few other thigs.

If i include like this

``````#include <iostream>
#include <fstream.h>
#include <vector>
#include <cmath>``````

It doesn't complain about the vectors but, for some reason ios and app on the following line are undeclared

``file.open ( outputPath, ios::app );``

Just update GCC.
I am quite confused by this :)

mrnutty 761

You can delete line 158 and 193. Also quoted strings i.e `"quotedStrings"` are automatically null terminated via compiler, so you don't have to manually add null character like you did here `"-c\0"`

You can delete line 158 and 193. Also quoted strings i.e `"quotedStrings"` are automatically null terminated via compiler, so you don't have to manually add null character like you did here `"-c\0"`

I also thought so, but I didn't work. I tried checking it and the input argument and the compared "-X" weren't the same size. I guess something is wrong with my compiler settings. Thanks anyway :)

off after reaching sqrt(n) instead of n, in isPrime(), applies
find

std::vector<int> primes = find ( value, false, NULL, true );

should be

std::vector<int> primes = find ( sqrt(value), false, NULL, true );

since you don't need primes beyond sqrt(value) to do the prime factorization
of value.

However, you can do even better by NOT getting all the primes first.
If the number is large, and has some factors, you will do better by
just finding the next prime up, and testing it, then dividing down the
number by that prime. Further, if your test for divisibility of the
number succeeds, after you should divide down the number, you should test again,
until you use up this factor entirely. In this way, you can avoid
a large prime search entirely for a number which is a high power
of some small primes, like 2^10.

off after reaching sqrt(n) instead of n, in isPrime(), applies
find

std::vector<int> primes = find ( value, false, NULL, true );

should be

std::vector<int> primes = find ( sqrt(value), false, NULL, true );

since you don't need primes beyond sqrt(value) to do the prime factorization
of value.

However, you can do even better by NOT getting all the primes first.
If the number is large, and has some factors, you will do better by
just finding the next prime up, and testing it, then dividing down the
number by that prime. Further, if your test for divisibility of the
number succeeds, after you should divide down the number, you should test again,
until you use up this factor entirely. In this way, you can avoid
a large prime search entirely for a number which is a high power
of some small primes, like 2^10.

Don't know if I agree with the call find( sqrt( value ) , false, NULL , true ) because then isPime will be working with the second root since find calls isPrim on line 73.

The other point you made is great, I'll be sure to implement that. It's gonna save up a lot of memory and CPU power, weird how I didn't do it that way in the first place since that's how you would do it on paper.

It looks to me like you would never need primes larger than sqrt(value), in the call to find() on line 104. Why do you want them?

It looks to me like you would never need primes larger than sqrt(value), in the call to find() on line 104. Why do you want them?

I don't see why that would be, but in any case it doesn't matter since as you already pointed out getting all primes less than the value is redundant anyways.

EDIT: Just realized why you are correct about that.

mrnutty 761

Don't know if I agree with the call find( sqrt( value ) , false, NULL , true ) because then isPime will be working with the second root since find calls isPrim on line 73.

The other point you made is great, I'll be sure to implement that. It's gonna save up a lot of memory and CPU power, weird how I didn't do it that way in the first place since that's how you would do it on paper.

If you want to save CPU power, then consider looking at faster algorithms. The prim tester you have runs in n*sqrt(n). To start, have a look at http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes for finding primes.

Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.