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.

If you have any improvements or ideas please leave a comment.

Cheers K0ns3rv

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.

If you have any improvements or ideas please leave a comment.

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);
}
```

deliezer
0
Newbie Poster

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.

Edited
by Reverend Jim because:
*
Fixed formatting *

K0ns3rv
0
Junior Poster in Training

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

I'll add that :D

K0ns3rv
0
Junior Poster in Training

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 :)

Edited
by K0ns3rv because:
*
n/a *

mrnutty
761
Senior Poster

`"quotedStrings"`

are automatically null terminated via compiler, so you don't have to manually add null character like you did here `"-c\0"`

K0ns3rv
0
Junior Poster in Training

`"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 :)

deliezer
0
Newbie Poster

The same thing I mentioned before, about cutting your search

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

equally well to your function find(); That is, your call to

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.

K0ns3rv
0
Junior Poster in Training

The same thing I mentioned before, about cutting your search

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

equally well to your function find(); That is, your call to

findstd::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.

deliezer
0
Newbie Poster

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?

K0ns3rv
0
Junior Poster in Training

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.

Edited
by K0ns3rv because:
*
n/a *

mrnutty
761
Senior Poster

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.