Writing out the first six prime numbers, we get 2, 3, 5, 7, 11, and 13. Obviously, the 6th prime is 13.

What is the 10001st prime number?

from math import * def Simple (n): if n < 2: return False if n == 2: return True limit = sqrt(n) div = 2 while div <= limit: if n % div == 0: return False div += 1 return True ind = 0 j = 0 numbers = [i for i in range (13, 10000000)] while ind <= 10001: if Simple(numbers[j]) and ind <= 10001: print (numbers[j]) ind += 1 j += 1
  • It is necessary to look for simple numbers, and not to check in the range whether the next number is simple. And you can not limit the range - the required may be greater than the border. - Akina
  • @Akina That is, you need to create a variable and it will be a simple number after each pass to increase it? - Monty Python
  • It is necessary to memorize all the found prime numbers - this will speed up and simplify the search for the next prime number. And the first few (2,3,5 and 7) can be hardcoded at all. - Akina
  • Zahardkodit? What is it like ? And still do not quite understand how to memorize it? - Monty Python
  • Zahardkodit? What is it like ? This will immediately define an array for simple ones with the first 4 values ​​filled, and not empty (well, or immediately insert the first 4). how to memorize it? simplenumbers[].append - Akina

1 answer 1

 from math import * def Simple (n): if n < 2: return False if n == 2: return True limit = sqrt(n) div = 2 while div <= limit: if n % div == 0: return False div += 1 return True Simple_Nums = [2,3,5,7,11,13] num = 14 while len(Simple_Nums) != 10001: if Simple (num): Simple_Nums.append (num) num += 1 print (max(Simple_Nums))
  • one
    It is not necessary to increase the div by 1, but it is necessary to increase by 2 (starting from 3). primes are odd and it makes no sense to check their divisibility by 2, 4, etc. It is even better to check divisibility for simple numbers from the Simple_Nums list (Eratosthenes sieve) - if the number is not divisible by 3, then it is not divisible by 6, 9, etc. - Enikeyshchik
  • one
    In the same way, num should be increased by 2 (starting from 15). Thus, the number of calculations will be halved - Enikeyschik
  • You @ Enikeyshik case says - use the Eratosthenen sieve or another algorithm (for example, Atkin sieve or Sundaram sieve). Various implementations of the sieve of Eratosthenes - MaxU