Question

Write a program that prints the count of all prime numbers between A and B (inclusive), where A and B are defined as follows:

A = The 5 digit unique number you had picked at the beginning of the semester

B = A + 5000

Just a recap on prime numbers: A prime number is any number, greater or equal to 2, that is divisible ONLY by 1 and itself. Here are the first 10 prime numbers: 2, 5, 7, 11, 13, 17, 19, 23, and 29.

Rules:

1. You should first create a boolean function called isPrime and use that function in your program. This function should take in any int and return true if the number is prime, otherwise, return a false. In the main body of your program, you should create a loop from A to B (inclusive) and use isPrime function to determine if the loop number should be counted or not.

2. Your program SHOULD NOT PRINT the individual prime numbers. You can print them for your own testing purpose, but in the final submission, comment out such print statements.

3. Your program SHOULD ONLY PRINT the answer -- which is a number.

4. Do not print extra characters in your answer (E.g. "answer=123" instead of 123)

the values for me:

A = 5000;

B = A+5000;

sample code to get started --->>>>>>>>>>

#include<iostream>
using namespace std;

bool isDivisibleBy(int num, int divisor) {
        // function returns true if num is divisible by divisor
        if(num % divisor == 0) {
                return true;
        } else {
                return false;
        }
}

bool isodd(int num) {
        // function returns true if num is odd
        if( isDivisibleBy(num,2) ) {
                return false;
        } else {
                return true;
        }
}


int main() {
        const int A = 1;
        const int B = 100;
        const int N = 17;
        
        int count = 0;
        
        // count of the numbers between A and B that are odd and divisible by N
        
        for(int i=A; i<=B; i++) {
                if( isDivisibleBy(i,N) && isodd(i) ) {
                        count++;
                }
        }
        
        // just print the answer and nothing else...
        cout << count << endl;

        return 0;
}

Answer 1

There are multiple ways to find if a number is a prime number or not. I'd suggest two such ways.

1. Would be the easy one. A direct approach. This would be to check all numbers from 2 to N(exclusive) and see if the number is divisible. If it is, its not a prime number, else it is

CODE:

#include<iostream>

using namespace std;

bool isprime(int n)
{
for(int i=2;i<n;i++) //taking a loop from 2 to n.
{
//if the number is divisible by any of the numbers between 2 and n, it is not prime and so we return false for it.
if(n%i==0)
return false;
}
return true;
}

int main()
{
int A=5000;
int B=A+5000;
int c=0;//used for count.
for(int i=A;i<=B;i++)
{
if(isprime(i)) //isprime function sending each value from A to B.
c++;
}
cout<<c<<endl;
}

#include<iostream>

using namespace std;

bool isprime(int n)
{
    for(int i=2;i<n;i++) //taking a loop from 2 to n.
    {
        //if the number is divisible by any of the numbers between 2 and n, it is not prime and so we return false for it.
        if(n%i==0)
            return false;
    }
    return true;
}


int main()
{
    int A=5000;
    int B=A+5000;
    int c=0;//used for count.
    for(int i=A;i<=B;i++)
    {
        if(isprime(i)) //isprime function sending each value from A to B. 
            c++;
    }
    cout<<c<<endl;
}

OUTPUT:

560

2. This is a time efficient approach. The one on top would take you O(n). This means that if a number turns out to be prime, it would have to calculate all value from 2 to n. Which is very inefficient. So, to tackle this and reduce the time complexity, I'll suggest a better approach, Its upto you to go with the approach of your choice.

#include<iostream>

using namespace std;

bool isprime(int n)
{
//these are boundary cases, not existent in your case since your numbers start from 5000
if(n<=1)
return true;
if(n<=3)
return false;
//We use this condition because a number is usually either divisible by 2 or 3, this is the most common case.
//Also, if we know a number is not divisible by 2 or 3, it is not divisible by 4. How does this help us?
//With this step, we just need to check for 5 and 7, between 1 to 10.
//So basically for every 10 divisions, we are reducing it to 4. Again between 10 to 20, we check 11, 13, 17, 19. The prime numbers, all others are checked.
if(n%2==0 || n%3==0)
return false;
//i*i because we just need to check for half the numbers, the other half repeat themselves.
for(int i=5;i*i<=n;i=i+6)
if(n%i==0 || n%(i+2)==0)
return false;
return true;
}

int main()
{
int A=5000;
int B=A+5000;
int c=0;//used for count.
for(int i=A;i<=B;i++)
{
if(isprime(i)) //isprime function sending each value from A to B.
c++;
}
cout<<c<<endl;
}

#include<iostream>

using namespace std;

bool isprime(int n)
{
    //these are boundary cases, not existent in your case since your numbers start from 5000
    if(n<=1)
        return true;
    if(n<=3)
        return false;
    //We use this condition because a number is usually either divisible by 2 or 3, this is the most common case.
    //Also, if we know a number is not divisible by 2 or 3, it is not divisible by 4. How does this help us?
    //With this step, we just need to check for 5 and 7, between 1 to 10.
    //So basically for every 10 divisions, we are reducing it to 4. Again between 10 to 20, we check 11, 13, 17, 19. The prime numbers, all others are checked.
    if(n%2==0 || n%3==0)
        return false;
    //i*i because we just need to check for half the numbers, the other half repeat themselves.
    for(int i=5;i*i<=n;i=i+6)
        if(n%i==0 || n%(i+2)==0)
            return false;
    return true;
}


int main()
{
    int A=5000;
    int B=A+5000;
    int c=0;//used for count.
    for(int i=A;i<=B;i++)
    {
        if(isprime(i)) //isprime function sending each value from A to B.
            c++;
    }
    cout<<c<<endl;
}

If you have any doubts or require any clarification, please leave a comment and i will answer it as soon as possible. Thank you :)