By default we limit the dominant primes we are looking for to a maximum value of

Question

By default we limit the dominant primes we are looking for to a maximum value of 10121012. Note that it means that you may not be able to determine if some numbers are dominant primes. In this case, don't print them. With maxprime=1012maxprime=1012, the expected run time should be around or less than a minute. Performance will be taken into account in the mark. Furthermore, your function (or any part of your code) should:

   not store hard-coded/precomputed primes,

   not use more than constant-size memory (i.e. it should be independent of the input),

   not necessarily print the numbers in any particular order.

Given a positive integer xx and its decimal notation dndn1…d1d0dndn1…d1d0 (didi corresponds to a digit), we say xx is a dominant prime if and only if:

x is prime,

for any index k{0,…,n},dk…d0k{0,…,n},dk…d0 is prime,

for any digit dn+1{1,…,9}dn+1{1,…,9}, dn+1dn…d0dn+1dn…d0 is not prime.

For example:

2 is a dominant prime, as it is prime, and any number ending by 2 is divisible by 2, and therefore not prime.

3 is not a dominant prime, since 13 is prime.

7937 is also a dominant prime, as 7937, 937, 37 and 7 are prime, and 17937, 27937, 37937, 47937, 57937, 67937, 77937, 87937, 97937 are not prime.

Write a recursive algorithm which enumerates dominant primes. Your algorithm should print dominant primes as it finds them (rather than at the end).

Explanation / Answer

#Returns whether a given num is prime or not

def is_prime(num):

flag = 2

maxflag = int(math.sqrt(num))

while flag <= maxflag:

if num % flag == 0:

return False

if num == 2:

flag += 1

else:

flag += 2 #Even numbers should not be considered

return (n != 1) #If num is 1, then we have found a factor, hence not prime

def check_add_digit(num,len):

result = []

for i in range(1,10):

if is_prime( i*10**(len) + num ):

res.append(i*10**(len) + num)

return result

def step(list_prime,length):

## Under 10^12

if length > 12:

return None

for prime in list_prime:

res = check_add_digit(prime,length)

if len(res) == 0:

#We have a dominant prime stop

print(prime)

else:

#We do not have a dominant prime but a list of candidates for length +1

step(res,length+1)

Related Questions

Navigate

• Browse (All)
• Browse B
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.