DMOPC '17 Contest 5 P3 - Mimi and Primes

View as PDF
Submit solution
Points: 7 (partial)
Time limit: 1.0s
Memory limit: 128M
Author:
Kirito
Problem type

In math class, Mimi learned about primes! To test her knowledge, her teacher assigned her the following problem for homework:

Given an array A of N elements, determine the largest prime number which divides every element of the array, or DNE if no such prime exists.

Mimi was sleeping in class, so she has no idea how to approach this problem! Can you write a program to help her finish her homework?

Python users are recommended to use PyPy over CPython. There is a significant performance increase.

Constraints

Subtask 1 [10%]

1 \le N \le 300
1 \le A_i \le 300

Subtask 2 [90%]

1 \le N \le 10^5
1 \le A_i \le 10^{15}

Input Specification

The first line of input will contain a single integer, N.
The next line of input will contain N space separated integers, A_1, A_2, \dots, A_N.

Output Specification

The output should consist of a single line, either the largest prime which divides all elements in the array, or DNE if no such prime exists.

Sample Input

5
6 12 18 24 30

Sample Output

3

Comments


  • 0
    herro  commented on Aug. 13, 2020, 3:44 p.m. ← edited

    so sad ;( tle'd case 27. Is there any way to make my code any faster? Or is it wrong?


    • -1
      Kirito  commented on Aug. 13, 2020, 11:27 p.m.

      Consider the case where res is the square of a prime.


  • -2
    AryanG  commented on Sept. 30, 2019, 2:48 p.m.

    I'm getting a TLE on Case #7 with C although I think I am using the optimal algorithm. Does anyone know certain points I might be missing?


    • -6
      Tzak  commented on Oct. 2, 2019, 2:00 a.m. ← edit 2

      This comment is hidden due to too much negative feedback. Show it anyway.


      • 0
        AryanG  commented on Oct. 2, 2019, 10:22 p.m.

        Thanks. It was the integer overflow error.


      • -3
        AryanG  commented on Oct. 2, 2019, 10:20 p.m. ← edited

        It would print squared numbers until the squared number is >= 3_000_000_000. Would it just take too long? Is the int too small?


  • 0
    AlanL  commented on Aug. 23, 2018, 3:20 a.m.

    I don't know why my code is producing a input mismatch exception....


    • 3
      zxyl  commented on Aug. 23, 2018, 4:32 a.m.

      Each A_i can be up to 10^{15}, which does not fit in an int. You'll need long to pass.


  • -15
    nickflyers18  commented on March 28, 2018, 7:47 p.m.

    This comment is hidden due to too much negative feedback. Show it anyway.


    • 28
      JohnWinter  commented on March 28, 2018, 7:56 p.m.

      1 is not a prime number