1084: Псевдопрості


Submit solution


Points:5
Time limit:1.0s
Memory limit:64M
Author:

Problem type

Натуральне число N назвемо «псевдопростим», якщо сума його дільників є числом простим.

Формат вхідних даних

У вхідному потоці дається одне натуральне число N (N <= 2*10^9).

Формат вихідних даних

У вихідний потік вивести «YES», якщо це число є «псевдопростим» і «NO» в протилежному випадку.

Приклад вхідних даних

2

Приклад вихідних даних

YES

Comments


  • 0
    maks00x
     commented on Feb. 18, 2020

    0, 1, саме число вважаються дільниками???


    • 0
      zvit
       commented on Feb. 18, 2020 edited

      0 не може бути дільником, а 1 та n враховувати


      • 0
        maks00x
         commented on Feb. 20, 2020

        Дякую!


  • 0
    Nibiru_crs
     commented on Feb. 7, 2019

    Розпишіть, будь ласка, покроково приклад з числом "2" та "4".


    • 0
      rrrrrrrrrrrrr
       commented on Nov. 24, 2020

      2 ділиться на 1 і на 2.Сума дільників = 3.3 є простим числом


  • 0
    Mpasa4186_G2
     commented on Dec. 17, 2017

    Як тут швидше можна зробити?


    • 4
      AHDPIYKO_KUTS
       commented on Feb. 21, 2018 edited

      за О(\(N^(1/2)\)) (за корінь) знайти всі дільники та просумувати їх та потім за О(\(N^(1/2)\)) перевірити суму на простоту.

      просто не потрібно перебирати всі числа до N та дивитися чи вони ділятся, потрібно так дивитися лише для чисел як меньші або дорівнюють корню з N та, якщо число є дільником від N просто додавати це число \(x\) до суми та додавати \(N / x\). Досить подібним способом робится перевірка на простоту.