Prime Crime 2

Computer Science Level 4

How many primes $p$ less than $10^{5}$ exist such that:

$p\bmod {10^4},p\bmod {10^3},p\bmod {10^2}$ and $p\bmod {10}$ are also prime?

As an explicit example, 2017 is one of them since 2017,17 and 7 are all prime.

Hint: The answer is a perfect square.

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

The answer is 625.

2 solutions

Soumava Pal
Feb 1, 2016

Here is my code, http://ideone.com/ruFRSR

@Prasun Biswas Please tell me about the primality testing algorithm you were talking about. I used the simplest one that I know, one that check all integers to sqrt(n).

Yeah, that's the trial division approach that you used. Good thinking for using a DP approach to make it more efficient. But even this will become slow with increase in input (range till you need to test)

If you modify your code to take the range as input from user and input $10^6$ , you'll see the relative difference between the efficiency of the algorithms.

Your code

My code

Both give the correct answer of $4184$ when you input $10^6$ but your code takes ~9 secs and my code takes ~1.5 secs. See the difference?

Now, speaking of those algorithms, there are many primality testing algorithms, each with their own advantages and disadvantages. For the problem here, the best approach is to store a list of primes below the range and then test which of those primes satisfy the problem criteria, hence using a sieving approach works best. The sieve I used is called the Sieve of Eratosthenes . There are many other sieves but this one's the easiest to implement.

There are also other pseudoprimality (probabilistic) testing algorithms like Fermat primality test, Miller Rabin primality test, etc and deterministic tests like Lucas-Lehmer, etc. You can read about some of them in the Primality testing wiki .

Prasun Biswas - 5 years, 4 months ago

Exactly, I know that it is going to eat up too much of runtime for bigger inputs, that is why I wanted to know what algorithm you used. I have heard of the Sieve of Eratosthenes but never implemented it. Nice solution. It takes O(n) space complexity, right? It will show memory overflow for huge input but I think it will work fine till 10^8.

Soumava Pal - 5 years, 4 months ago

Yup, the classic sieve of Eratosthenes has a space complexity of $O(n)$ . Without deteriorating the runtime, we can reduce the space complexity to $O(\sqrt n)$ using the segmented sieve of Eratosthenes but reducing the space complexity furthermore will cause runtime to deteriorate.

If space complexity is even more of an issue, you can use the Sieve of Sorenson which has a worse runtime but better space complexity.

Prasun Biswas - 5 years, 4 months ago

@Prasun Biswas – Yes, I read about it in the Wiki link up there. :) Thanks a lot. I was looking for a code on primality testing for a long time besides the one I do.

Soumava Pal - 5 years, 4 months ago

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<100000; i++){
            if (is_prime(i)
                            && is_prime(i%10000)
                            && is_prime(i%1000) 
                            && is_prime(i%100)
                            && is_prime(i%10)){
                c++;
            }
        }
        cout<<c<<endl;
        return 0;
    }

Output:

625

What was the run-time of your code with that is_prime() function?

Prasun Biswas - 5 years, 4 months ago

Well.. in worst case.. it runs $\frac{n}{2}-1$ times. But the problem is with the numbers that are too long greater than $10^5$ . Hence the function given by me is easy to understand but not efficient.

Zeeshan Ali - 5 years, 4 months ago

I'm not asking about theoretical time complexity of your code. I'm asking about the actual average run-time (in seconds) of your code.

Prasun Biswas - 5 years, 4 months ago

@Prasun Biswas – Well.. the time you are asking may differ due to different hardware architectures. Our focus is the Efficiency of a code which in this case is $O(\frac{n}{2})$

Zeeshan Ali - 5 years, 4 months ago

@Zeeshan Ali – I know that. I assume you have a PC with an average configuration like mine, so I wanted a rough estimate of how much time it took for you to highlight how much inefficient the trial division approach is (without delving much into time complexity and stuff)

Simple sieving and using a hash-table (dictionary in python, I think) to store the sieving results and use for condition checking should yield much better results.

Prasun Biswas - 5 years, 4 months ago

@Prasun Biswas – How much time does yours take ?

Zeeshan Ali - 5 years, 4 months ago

@Zeeshan Ali – Roughly 0.3 seconds. Here's the code (Python 3.5) :

from time import process_time as time
def primeset(n):
    myset=set()
    tstlist=[0]*(n+1)
    for i in range(2,n+1):
        if tstlist[i] == 0:
            myset.add(i)
            for j in range(i,n+1,i):
                tstlist[j]=1
    return myset

def test(p,myset):
    return all({int(str(p)[-i:]) in myset for i in range(1,len(str(p)))})

st=time()
prime_set=primeset(int(input('Enter range = ')))
count=0
for p in prime_set:
    count+=test(p,prime_set)
print('\nAnswer is %d' %count)
print('\nApproximate Runtime = %.2f seconds' %(time()-st))

Output:

Enter range = 100000

Answer is 625

Approximate Runtime = 0.31 seconds

Prasun Biswas - 5 years, 4 months ago

Prime Crime 2

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

The answer is 625.

2 solutions

0 pending reports