Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Prime Number Generating Puzzle (Edge Cases)

Tags:

python

primes

I'm solving the following problem on a coding site. It's failing for some edge cases on the tests (hidden tests), but I'm not sure what they are. Anyone see any issues with this?

Problem: Let A be a string of all the prime numbers sequentially squashed together (i.e. 235711131719...). Given an index n, return a string of 5 digits where the first digit is at index n in A.

e.g. foo(0) => 23571 and foo(10) => 19232

Here's my code:

def gen_primes():                                                                                                                                                                                                    
    A = {}                                                                                                                                                                                                           
    i = 2                                                                                                                                                                                                            
    while True:                                                                                                                                                                                                      
        if i not in A:                                                                                                                                                                                               
            yield i                                                                                                                                                                                                  
            A[i * i] = [i]                                                                                                                                                                                           
        else:                                                                                                                                                                                                        
            for p in A[i]:                                                                                                                                                                                           
                A.setdefault(p + i, []).append(p)                                                                                                                                                                    
            del A[i]                                                                                                                                                                                                 
        i += 1                                                                                                                                                                                                       

def answer(n):                                                                                                                                                                                                       

    counter = 0                                                                                                                                                                                                      
    prime_string = ""                                                                                                                                                                                                

    for p in gen_primes():                                                                                                                                                                                           
        if (counter >= n):
            prime_string += str(p)                                                                                                                                                                                   
        counter += len(str(p))                                                                                                                                                                                       
        if len(prime_string) >= 5:                                                                                                                                                                                   
            break                                                                                                                                                                                                    

    return prime_string[:5]    
like image 513
user7373175 Avatar asked Jan 04 '17 08:01

user7373175


People also ask

Is there trick to finding prime numbers?

To prove whether a number is a prime number, first try dividing it by 2, and see if you get a whole number. If you do, it can't be a prime number. If you don't get a whole number, next try dividing it by prime numbers: 3, 5, 7, 11 (9 is divisible by 3) and so on, always dividing by a prime number (see table below).

What is the biggest prime number ever found?

The largest known prime number (as of September 2022) is 282,589,933 − 1, a number which has 24,862,048 digits when written in base 10. It was found via a computer volunteered by Patrick Laroche of the Great Internet Mersenne Prime Search (GIMPS) in 2018.

How do you find the algorithm for prime numbers?

Algorithm to Find Prime NumberSTEP 1: Take num as input. STEP 2: Initialize a variable temp to 1. STEP 3: Iterate a “for” loop from 2 to sqrt(num). STEP 4: If num is divisible by loop iterator, then update temp value to 0.

What is the fastest way to check if a number is prime?

Simple methods. The simplest primality test is trial division: given an input number, n, check whether it is evenly divisible by any prime number between 2 and √n (i.e. that the division leaves no remainder). If so, then n is composite. Otherwise, it is prime.


1 Answers

I think this could break for primes with more than one digit:

Let's assume that we have arrived at primes with three digits, like 103. Counter is 10 and n is 11 (this is just an example, I don't know if this exact constellation would turn up)

Then we would need to use the digits "03" out of "103". But since counter is smaller than n, the entire prime is skipped. The program would continue with 107.

You could fix this by removing counter entirely: Always add primes to the string, break out of the loop if the length of the string is n+5 or more.

EDIT:

I've checked your code: An example is answer(5) and answer(6). With your code, both calls result in "13171". The second digit of "11" is skipped.

With this code:

def answer(n):                                                                                                                                                                                                       

    counter = 0                                                                                                                                                                                                      
    prime_string = ""                                                                                                                                                                                                

    for p in gen_primes():
        prime_string += str(p)                                                                                                                                                                                     
        if len(prime_string) >= n+5:                                                                                                                                                                                   
            break                                                                                                                                                                                                    

    return prime_string[n:n+5] 

They result in

11317  # answer(5)
13171  # answer(6)
like image 156
lhk Avatar answered Oct 21 '22 10:10

lhk