Prime Crime 4

Computer Science Level 3

What is the greatest integer z z less than 1 0 5 10^{5} such that both z z and the sum of digits of z z are prime ?

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


The answer is 99991.

Zeeshan Ali by Zeeshan Ali , 25, Pakistan

This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try refreshing the page, (b) enabling javascript if it is disabled on your browser and, finally, (c) loading the non-javascript version of this page . We're sorry about the hassle.

3 solutions

Bill Bell
Jan 23, 2016 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
 
from gmpy2 import is_prime

def sum_digits(n):
    r = 0
    while n:
        r, n = r + n % 10, n / 10
    return r

max_z=0
for z in (_ for _ in range(2,10**5) if is_prime(_) and is_prime(sum_digits(_))):
    max_z=max(max_z,z)

print max_z

1 Helpful 0 Interesting 0 Brilliant 0 Confused

what is the algorithm behind the function is_prime ?

Zeeshan Ali - 5 years, 4 months ago

Log in to reply

I don't know.

Bill Bell - 5 years, 4 months ago

It's better to go down from 1 0 5 10^5 . 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
 
from gmpy import is_prime as p
def f(n):
    if not p(n):return False
    li=list(str(n))
    su=0
    for i in li:
        su+=int(i)
    if p(su):return True
    return False
for i in range(100000,0,-1):
    if f(i):break
print(i)

(Time:8.2 ms)

0 Helpful 0 Interesting 0 Brilliant 0 Confused
Zeeshan Ali
Jan 23, 2016

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

1
2
3
4
5
6
7
8
 
    bool is_prime(int N){
        for (int i=2; i<N/2; i++){
            if (N%i==0){
                return false;
            }
        }
        return true;
    }

I leave the further work on you all, if you don't mind :)

0 Helpful 0 Interesting 0 Brilliant 0 Confused

a) You don't need to test till N/2 . Testing till sqrt(N) , or equivalently with the test condition i*i<=N suffices. Why? See this problem.

b) Your is_prime() uses trial division which is an inefficient method and will take a longer run-time as N increasing. To be precise, your is_prime has O ( N ) O(N) time complexity. Try using faster primality tests like Miller-Rabin which has an average time complexity of O ( log ⁡ 3 N ) O(\log^3 N) .

Prasun Biswas - 5 years, 4 months ago

In many cases we need can generate all the prime numbers in a range and then use some efficient search method to determine whether a given number in the range is equal to one of those primes. You might be interested in one of the pieces of Python software I happened upon just yesterday.

Actually it's written in C++ but it's accessible from Python. It's available at https://pypi.python.org/pypi/pyprimesieve. Very, very fast.

Bill Bell - 5 years, 4 months ago

0 pending reports

×

Problem Loading...

Note Loading...

Set Loading...