Finding Primes Between Two #'s

[WillMalina]

I am currently making a program that has the user input two numbers. My program will find all the primes in between the inputted numbers. This is what I have:

#include <iostream>
using namespace std;

int get_prime(int a, int b){
    //takes user input and loops through all number between a and b testing if they are prime
    while (a <= b) {
          if (a % 2 != 0 && a % 3 != 0 && a % 4 != 0 && a % 5 != 0 && a % 6 != 0 && a % 7 != 0 && a % 8 != 0 && a % 9 != 0) {
                cout << a << " is prime" << endl;
                }
          ++a;
          }
               
    //if prime output, if not dont out put
    return 0; // <---- possible bug?
}

int main() {
    //set up variables to hold user input
    int num_1, num_2;
    //ask for Input
    cout << "Type two integers, I will display all prime numbers in between these two numbers" << endl;
    cout << "Press enter after typing each number" << endl;
    cout << "First Number: ";
    //take input
    cin >> num_1;
    cout << "Second Number: ";
    cin >> num_2;
    //call function get_prime passing input as parameters
    get_prime(num_1, num_2);
    cin.ignore();
    cin.get();
    return 0;
}

Now it works fine and all but I have 2 questions.

First:

 while (a <= b) {
          if (a % 2 != 0 && a % 3 != 0 && a % 4 != 0 && a % 5 != 0 && a % 6 != 0 && a % 7 != 0 && a % 8 != 0 && a % 9 != 0) {
                cout << a << " is prime" << endl;
                }
          ++a;
          }

Is there a possible way to loop through the conditions of the if statement so that I don't have to write all those conditions? Like a way that I can make a counter that acts as a divisor to a?

When I tried doing this I couldn't find a way to be able to test whether it was prime or not.

Second:

Do I have to return a value at the end of my get_prime function? Or is it not necessary because I am outputting the prime numbers within that function?

Any help would be appreciated.

Thanks,
Will Malina

[atropos]

answer to the first question:
If a%2 != 0, then a%4 != 0, a%6 !=0, and a%8 !=0 will all be true as well, so their inclusion in the if statement are unnecessary. Same thing applies to a%3!=0 and a%9!=0.

as for the second question:
No, you do not have to return a value. If you plan on doing all the output within a function, preface the function declaration/definition with void.

[WillMalina]

Thanks for the quick response!

I guess I should've used some common sense in the first one haha *facepalm*

Now I am planning on using this program to solve Project Euler Problem 10: "The sum of the primes below 10 is 2 + 3 + 5 + 7 = 17.

Find the sum of all the primes below two million."

I think I can easily modify my program to meet these requirements. Here is what I have:

#include <iostream>
using namespace std;

void get_prime(long long a, long long b){
    //takes user input and loops through all number between a and b testing if they are prime
    //make variable to hold total sum
    long long sum = 0; 
    while (a <= b) {
          if (a % 2 != 0 && a % 3 != 0 &&  a % 5 != 0  && a % 7 != 0) {
                a += sum; //add a to sum
                }
          ++a;
          }
    //Output final sum
    cout << sum;
}

int main() {
    //set up variables to hold user input
    long long num_1, num_2;
    //ask for Input
    cout << "Type two integers, I will display all prime numbers in between these two numbers" << endl;
    cout << "Press enter after typing each number" << endl;
    cout << "First Number: ";
    //take input
    cin >> num_1;
    cout << "Second Number: ";
    cin >> num_2;
    //call function get_prime passing input as parameters
    get_prime(num_1, num_2);
    cin.ignore();
    cin.get();
    return 0;
}

However my output ends up simply being "0" when I input the numbers 1 and 2 million. I thought that by changing the type of my variables from int to long long I would be able to fix my issue however that did nothing.

Any ideas?

[long double main]

To check if a number is prime, you need to check if it's divisible by any integer less than the square root of the number.

It would be something like

bool isPrime(int num)
{
    bool prime = true;
    for (int i = 2; i < sqrt(num); ++i)
        /* check for divisibility here, and set prime to false if it's divisible */
    return prime;
}

(you'll need to #include <cmath> in order to use the sqrt function)
(you can speed it up by just checking for divisibility by 2, and then the odd integers)

And then in your get_prime function, you would loop through all the numbers from a to b, calling isPrime and outputting if it's prime.

Of course, the best way to do this would probably be to use a prime sieve, but that may or may not be beyond what you are currently capable of doing....

[Need4Sleep]

Long double you dog! just about wrote that same block of code.

[WillMalina]

Alright thanks for setting me on the right track.

I will look up an example of a prime sieve sometime tomorrow.

[WillMalina]

Alright I seem to have made a successful test. All my test numbers have worked so far.

void primetest(int a, int b) {
while (a<=b) {
int prime=sqrt(a);
for (int i = 2; i<=sqrt(a);++i){ 
if (a%i==0) {
++a;
break;
}
else if (a%i!=0) {
--prime;
}
} 
if (prime == 1) {
cout<<a<<" is prime."<<endl;
++a;
}
}
}

Sorry for the lack of indentation but I wrote this all and tested it all on my iPhone (can't get to my computer as I am at school right now).

Any ideas on either something that is wrong with my code or something that can be improved?

[ResidentBiscuit]

tested it all on my iPhone

how?? Is there an app to compile C++ code?

[WillMalina]

Yes, it's called C++ Programming Language. There's a lite version but that doesn't let you input anything.

[Moschops]

It doesn't compile the code - it uses an online compiler to do it. You might as well just use a web browser for your online compiler of choice.

[Stewbond]

http://itunes.apple.com/nl/app/c++-programming-language/id461327665?mt=8

Interesting

[WillMalina]

Either way, whether it compiles it or not, it's a handy tool for when you're away from your computer and you get the itch to program.

[Shinigami]

I think class would be better then function for prime number operation if you know object Oriented programming. I have a class for prime numbers.

[Moschops]

Either way, whether it compiles it or not, it's a handy tool for when you're away from your computer and you get the itch to program.

Provided, that is, that you have such a communications device on you, in which case you might as well just SSH|rlogin|telnet|rsh into your server of choice and code as if you were sitting at its keyboard, much as people have been doing for the past couple of decades :)

[naraku9333]

@Moschops
I wouldn't find that convenient if I only want to test a code snippet. I use IDEdroid for this, which uses IDEone, I do agree with anything non-trivial.
As a side note to android users, there is an app to write compile and run an android app. AIDE, just found it myself, looks interesting though its unlikely Ill go through the trouble of writting an android app on my phone.

[Sealey]

A dynamic programming approach is always the best imo. Here is what I came up with.

Be sure to replace the initial value of A>=0 and B<=100000 to your lower and upper bounds.

#include <cstdlib>
#include <cmath>
#include <string.h>
int num[100000];
using namespace std;
int totalPrimes(int a){
	if(num[a]==1) return 1;
	else if(num[a]) return num[a];
	for(int i=2;i<=a/2;i++)
	{
		if(a%i==0){
		 num[a] = 1+totalPrimes(a/i);
		 return num[a];
		}
	}
	return 0;
}
void sieve(int n) {
	num[0]=0;
	num[1]=0;
	int m=(int)sqrt(n);
	for (int i=2; i<=m; i++) 
		if (num[i])
			for (int k=i*i; k<=n; k+=i) 
				num[k]=0;
}
int main(){
	// Set A equal to your LOWER bound
	int A = 0;
	// Set B equal to your UPPER bound
	int B = 20; 
	
	int result=0, total=0;
	for(int i=0; i < 100000; i++) num[i] = 1;
	sieve(B);
	for(int i=A; i <= B; i++)
	{
		total = totalPrimes(i);
		if(total>1 && num[total]==1) result +=1;
	}
	return result;
}

[Need4Sleep]

Maybe this will help, heres a project euler program i wrote involving primes:

#include <iostream>
/*By listing the first six prime numbers: 2, 3, 5, 7, 11, and 13, we can see that the 6th prime is 13.
What is the 10 001st prime number?
ANSWER:104,743
*/
int main()
{
    const int max = 10001;
    int count = 0;
    int i, j;

    for (i = 2; ; i++) {
            for (j = 2; j < i; j++)
                    if (i % j == 0)
                            break;
            if (i == j) {
                    count++;
                    if (count == max)
                            break;
            }
    }
    std::cout << max << "st prime number is: " << i;
}