## DMOPC '17 Contest 5 P3 - Mimi and Primes

View as PDF

Points: 10 (partial)
Time limit: 1.0s
Memory limit: 128M

Author:
Problem type
Allowed languages
Ada, Assembly, Awk, Brain****, C, C#, C++, COBOL, CommonLisp, D, Dart, F#, Forth, Fortran, Go, Groovy, Haskell, Intercal, Java, JS, Kotlin, Lisp, Lua, Nim, ObjC, OCaml, Octave, Pascal, Perl, PHP, Pike, Prolog, Python, Racket, Ruby, Rust, Scala, Scheme, Sed, Swift, TCL, Text, Turing, VB, Zig

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

Given an array of 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.

#### Input Specification

The first line of input will contain a single integer, . The next line of input will contain space separated integers, .

#### 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

• commented on Aug. 13, 2020, 11:44 a.m. edited

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

• commented on Aug. 13, 2020, 7:27 p.m.

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

• commented on Sept. 30, 2019, 10:48 a.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?

• commented on Oct. 1, 2019, 10:00 p.m. edited

Consider the following C program:

#include <stdio.h>

int main() {
long long n = 3000000000;
for(int i = 44444; i * i <= n; i++) {
printf("%d\n", i * i);
}
}

What do you think will happen?

• commented on Oct. 2, 2019, 6:22 p.m.

Thanks. It was the integer overflow error.

• commented on Oct. 2, 2019, 6: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?

• commented on Aug. 22, 2018, 11:20 p.m.

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

• commented on Aug. 23, 2018, 12:32 a.m.

Each can be up to , which does not fit in an int. You'll need long to pass.

• commented on March 28, 2018, 3:47 p.m.

This comment is hidden due to too much negative feedback. Click here to view it.

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

1 is not a prime number