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]
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).
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.
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.
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.
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)
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With