profile
Размещено 4 года назад по предмету Информатика от innakonstantin

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

  1. Ответ на вопрос
    Ответ на вопрос дан nelle987
    Учитывая, что 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) находить нужное число в памяти.
    1. Ответ на вопрос
      Ответ на вопрос дан innakonstantin
      спасибо большое:)
Не тот ответ на вопрос, который вам нужен?
Найди верный ответ
Самые новые вопросы
tegysigalpa2012
Русский язык - 5 лет назад

Помогите решить тест по русскому языку тест по русскому языку «местоимение. разряды местоимений» для 6 класса 1. укажите личное местоимение: 1) некто 2) вас 3) ни с кем 4) собой 2. укажите относительное местоимение: 1) кто-либо 2) некоторый 3) кто 4) нам 3. укажите вопросительное местоимение: 1) кем-нибудь 2) кем 3) себе 4) никакой 4. укажите определительное местоимение: 1) наш 2) который 3) некий 4) каждый 5. укажите возвратное местоимение: 1) свой 2) чей 3) сам 4) себя 6. найдите указательное местоимение: 1) твой 2) какой 3) тот 4) их 7. найдите притяжательное местоимение: 1) самый 2) моего 3) иной 4) ничей 8. укажите неопределённое местоимение: 1) весь 2) какой-нибудь 3) любой 4) этот 9. укажите вопросительное местоимение: 1) сколько 2) кое-что 3) она 4) нами 10. в каком варианте ответа выделенное слово является притяжательным местоимением? 1) увидел их 2) её нет дома 3) её тетрадь 4) их не спросили

Информация

Посетители, находящиеся в группе Гости, не могут оставлять комментарии к данной публикации.