Question

Придумайте алгоритм,находящий N-ное простое число, если N<50

Answer 1

Учитывая, что 50 - это очень немного (50-е простое число всего лишь 229), можно придумать всё что угодно (даже ужасающе неэффективное).
Можно просто перебирать все числа, начиная с двойки, и каждое делить на все меньшие его, начиная с двойки. Если хоть на одно разделится - не простое, иначе простое. Попутно подсчитывая число простых чисел, N-е найти не составит труда.

Псевдокод:
ввод N
i = 2
counter = 0
нц
   для j = 2..(i - 1)
      если i mod j = 0 тогда
         увеличить i на 1
         следующая итерация внешнего цикла
      увеличить counter на 1
      если counter = N тогда
         вывод i
         завершение работы программы
   увеличить i на 1
кц

Дальше можно изменять эту программу, оптимизировать. Например, известно, что меньший собственный делитель любого составного числа не превосходит корня из этого числа, следовательно, можно во внутреннем цикле делать перебор не до i - 1, а до [sqrt(i)].
Другое полезное наблюдение может заключаться в том, что все простые числа кроме 2 имеют вид 6m - 1 или 6m + 1 (остальные не подходят: очевидно, 6n делится на 6, 6n +-2 четные числа, а 6n + 3 делится на 3). Это наблюдение позволит примерно в три раза сократить число итераций внешнего цикла.
Наконец, можно сохранять все встретившиеся простые числа в массив, и затем проверять, делится ли текущее число на простые числа, меньшие себя: если не делится, то оно - тоже простое. Для хранения 50 маленьких натуральных чисел в памяти не нужно много места.
Можно воспользоваться каким-нибудь другим алгоритмом, например, решетом Эратосфена. Но в зависимости от того, на каком языке программирования будет потом реализовываться этот алгоритм, он может записываться нетривиально. Для выполнения "на бумажке" решето Эратосфена - один из самых удобных способов.
В конце концов, можно использовать "читерский" метод - взять откуда-нибудь первые 50 простых чисел, записать их куда-нибудь, а потом просто за O(1) находить нужное число в памяти.

Answer 2

Алгоритм для нахождения N-го простого числа (N < 50)

Для нахождения N-го простого числа, можно использовать следующий алгоритм:

1. Создайте пустой список, в котором будут храниться простые числа. 2. Инициализируйте переменную `count` с значением 0, которая будет отслеживать количество найденных простых чисел. 3. Инициализируйте переменную `number` с начальным значением 2, которая будет использоваться для проверки чисел на простоту. 4. Пока `count` меньше `N`, выполняйте следующие шаги: - Проверьте, является ли `number` простым числом. - Если `number` является простым числом, добавьте его в список простых чисел и увеличьте `count` на 1. - Увеличьте `number` на 1. 5. Верните N-е простое число из списка простых чисел.

Пример реализации алгоритма на языке Python:

def is_prime(n):
    if n < 2:
        return False
    for i in range(2, int(n ** 0.5) + 1):
        if n % i == 0:
            return False
    return True

def find_nth_prime(N):
    primes = []
    count = 0
    number = 2

while count < N:
        if is_prime(number):
            primes.append(number)
            count += 1
        number += 1

return primes[N - 1]

N = 10
nth_prime = find_nth_prime(N)
print(f"The {N}-th prime number is: {nth_prime}")

Примечание: В данном примере алгоритма используется функция `is_prime(n)`, которая проверяет, является ли число `n` простым. Эта функция использует метод перебора делителей от 2 до квадратного корня из `n`. Если число делится на любой из этих делителей без остатка, то оно не является простым. Если число не делится ни на один из этих делителей, то оно является простым.

Пример работы алгоритма

Давайте рассмотрим пример работы алгоритма для нахождения 10-го простого числа.

1. Инициализируем пустой список простых чисел: `primes = []`. 2. Инициализируем переменную `count` с значением 0: `count = 0`. 3. Инициализируем переменную `number` с начальным значением 2: `number = 2`. 4. Проверяем число 2 на простоту. Оно является простым числом, поэтому добавляем его в список простых чисел и увеличиваем `count` на 1: `primes = [2]`, `count = 1`. 5. Увеличиваем `number` на 1: `number = 3`. 6. Проверяем число 3 на простоту. Оно является простым числом, поэтому добавляем его в список простых чисел и увеличиваем `count` на 1: `primes = [2, 3]`, `count = 2`. 7. Увеличиваем `number` на 1: `number = 4`. 8. Проверяем число 4 на простоту. Оно не является простым числом, поэтому пропускаем его. 9. Увеличиваем `number` на 1: `number = 5`. 10. Проверяем число 5 на простоту. Оно является простым числом, поэтому добавляем его в список простых чисел и увеличиваем `count` на 1: `primes = [2, 3, 5]`, `count = 3`. 11. Увеличиваем `number` на 1: `number = 6`. 12. Проверяем число 6 на простоту. Оно не является простым числом, поэтому пропускаем его. 13. Увеличиваем `number` на 1: `number = 7`. 14. Проверяем число 7 на простоту. Оно является простым числом, поэтому добавляем его в список простых чисел и увеличиваем `count` на 1: `primes = [2, 3, 5, 7]`, `count = 4`. 15. Увеличиваем `number` на 1: `number = 8`. 16. Проверяем число 8 на простоту. Оно не является простым числом, поэтому пропускаем его. 17. Увеличиваем `number` на 1: `number = 9`. 18. Проверяем число 9 на простоту. Оно не является простым числом, поэтому пропускаем его. 19. Увеличиваем `number` на 1: `number = 10`. 20. Проверяем число 10 на простоту. Оно не является простым числом, поэтому пропускаем его. 21. Увеличиваем `number` на 1: `number = 11`. 22. Проверяем число 11 на простоту. Оно является простым числом, поэтому добавляем его в список простых чисел и увеличиваем `count` на 1: `primes = [2, 3, 5, 7, 11]`, `count = 5`. 23. Увеличиваем `number` на 1: `number = 12`. 24. Проверяем число 12 на простоту. Оно не является простым числом, поэтому пропускаем его. 25. Увеличиваем `number` на 1: `number = 13`. 26. Проверяем число 13 на простоту. Оно является простым числом, поэтому добавляем его в список простых чисел и увеличиваем `count` на 1: `primes = [2, 3, 5, 7, 11, 13]`, `count = 6`. 27. Увеличиваем `number` на 1: `number = 14`. 28. Проверяем число 14 на простоту. Оно не является простым числом, поэтому пропускаем его. 29. Увеличиваем `number` на 1: `number = 15`. 30. Проверяем число 15 на простоту. Оно не является простым числом, поэтому пропускаем его. 31. Увеличиваем `number` на 1: `number = 16`. 32. Проверяем число 16 на простоту. Оно не является простым числом, поэтому пропускаем его. 33. Увеличиваем `number` на 1: `number = 17`. 34. Проверяем число 17 на простоту. Оно является простым числом, поэтому добавляем его в список простых чисел и увеличиваем `count` на 1: `primes = [2, 3, 5, 7, 11, 13, 17]`, `count = 7`. 35. Увеличиваем `number` на 1: `number = 18`. 36. Проверяем число 18 на простоту. Оно не является простым числом, поэтому пропускаем его. 37. Увеличиваем `number` на 1: `number = 19`. 38. Проверяем число 19 на простот