Prime Crime 1

Computer Science Level 3

What is the $the$ $number$ of primes $p$ less than 2016 such that both $p+4$ and $p+12$ are also prime ?

Hint:

It is also a prime number :)

this problem is a part of set Prime Crimes via Computer Science

The answer is 19.

2 solutions

Zeeshan Ali
Jan 23, 2016

Here is a C++ code to find whether a number is prime or not.

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

Here is the complete code in c++ :)

    #include<iostream>
    using namespace std;
    int main(){
        int c=0;
        for (int i=1; i<2016; i++){
            if (is_prime(i) && is_prime(i+4) && is_prime(i+12)){
                c++;
            }
        }
        cout<<c<<endl;
        return 0;
    }

Vijay Kumar
Jan 23, 2016

Use either sieve of eratosthenes or just a naive algo to check whether a number is prime or not. Then for each i that satisfies the condition, increment the answer and finally it will be 19.

How efficiently do these algorithms work to find if a number $n$ is prime?

Zeeshan Ali - 5 years, 4 months ago

If you use naive algo then to check whether a number is prime or not you have to check for n-2 numbers excluding 1 and n at worst case. So to check T cases of n's as prime or not, this algo took O(t*n) (I,e) if we need to check n numbers then overall complexity will be nearly O(n^2).

To reduce this complexity to nearest log factors, we are going with sieve of eratosthenes.

We know that if a number n is divisible by i where 1<i<n-1, then that n is composite and not prime. So just keep an array of size x where x is the largest 'n' that you are going to check whether prime or not. Initially make all the entries in it as 0(prime at first). Then carefully mark all the multiples of i where 1<i<n as 1(those are composite). We can furthur optimise this marking process just by leaving the already marked i's, because if i is already marked then all the multiples of that i should also be marked already. Now we are available with an array that says whether a particular index of that array is prime or not. This computation will take O(n (log n) loglog(n)) in the worst case and hence we reduced our complexity from O(n^2). This is how sieve efficiently works when we compare it with naive one.

Correct me if anything went wrong.

Vijay Kumar - 5 years, 4 months ago

Well.. I have not ever learned an algorithm for finding whether a number is prime or not. What I follow is a simple and efficient way below;

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

How does it work?

Assume a number $N=10$ , in this case the loop will run 5 times at-most and finds if there is a number $i$ from 2 to 4 both inclusive such that it divides 10 completely (i-e N mod i is 0) and if so, it returns false. Since 2 divides 10 completely the loop is terminated returning false :)

What do say about that ?

Zeeshan Ali - 5 years, 4 months ago

@Zeeshan Ali – This one, will yields the worst case complexity of O(n^2) though you are considering only N/2 numbers. This one can also be furthur optimized. If you know what does that loglog(n) say, then you can easily get what sort of optimisation, I'm talking about. Google it to learn furthur optimising ur procedure. here it is: Consider the number 8. The divisor of 8 will be found between 1 and sqrt(8) itself. Because the largest number that divides 8 will be 4 and which in turn 4 will get 2 as the such number that divides it. So instead of running the loop untill N/2, you can change it to sqrt(N). This is evident that if 4 is a multiple of 2 then the number x which is the multiple of 4 is also the multiple of 2.

Vijay Kumar - 5 years, 4 months ago

@Vijay Kumar – Yes.. you are right.. I am trying to learn the better approaches. And that is why I gave the set Prime Crimes via Computer Science . Thank you very much for your contributions :)

Zeeshan Ali - 5 years, 4 months ago

@Zeeshan Ali – All these prime crime problems are nice. Enjoyed solving it. Nice work dude keep it up!!! :-)

Vijay Kumar - 5 years, 4 months ago

@Vijay Kumar – I would like you to refresh your stats on Leader Board of this set :D

Zeeshan Ali - 5 years, 4 months ago

@Zeeshan Ali – Leaderboard is not showing. Completed all except prime crime 2 in this set. What is there in leaderboard?I cant able to see.

Vijay Kumar - 5 years, 4 months ago

@Vijay Kumar – Well.. I don't know why the leader board is not showing.. And still there is nothing it that.. I expect those who attempt my problems on sets given by me in the list of their respective leader boards :)

Zeeshan Ali - 5 years, 4 months ago

@Zeeshan Ali – I have realized that all my leader bords are empty due to some vague reasons. Please contact with Calvin Lin via calvin@Brilliant.org for that issue of "Leader Board is not opening!" for my set. Thanks

Zeeshan Ali - 5 years, 4 months ago

Prime Crime 1

this problem is a part of set Prime Crimes via Computer Science

The answer is 19.

2 solutions

0 pending reports