trang chủ / đề bài / icpc22_nat_c

Số nguyên tố liên tiếp

Đề bài

Mô tả

Có lẽ bạn đã biết số nguyên tố là một trong những khái niệm tuyệt vời nhất của lý thuyết số! Trong cuộc đời của mỗi lập trình viên thi đấu chắc chắn có rất nhiều bài toán về số nguyên tố, và đây là thêm một bài nữa!

Nhắc lại rằng số nguyên tố là số nguyên dương có đúng hai ước dương. 10 số nguyên tố nhỏ nhất là 2,3,5,7,11,13,17,19,23 và 29.

Trong bài toán này, một số nguyên dương n được gọi là "đẹp" khi và chỉ khi nó biểu diễn được dưới dạng tích của các số nguyên tố liên tiếp. Một cách hình thức, n là số đẹp khi và chỉ khi tồn tại dãy số nguyên p1,p2,…,pk thỏa mãn:

  • tất cả các số p1,p2,…,pk đều là số nguyên tố;
  • n=p1·p2·…·pk;
  • p1<p2<…<pk;
  • không tồn tại số nguyên tố x nào thỏa mãn pi<x<pi+1 (1≤i<k).

Theo định nghĩa trên, 2=2, 6=2·3, 30=2·3·5 và 210=2·3·5·7 là các số đẹp, còn 4=22, 10=2·5 và 20=22·5 thì không.

Cho một số số nguyên, hãy xác định số nào là số đẹp.

Dữ liệu vào

  • Dòng đầu tiên chứa số nguyên t.
  • t dòng tiếp theo, dòng thứ i chứa số nguyên ni.

Dữ liệu ra

In ra t dòng, dòng thứ i là NICE nếu ni là số đẹp, ngược lại là UGLY.

Ràng buộc

  • 1≤t≤105.
  • 1≤ni≤1019.

Ví dụ

Input Output Giải thích
10
1
2
3
4
5
6
7
8
9
10
UGLY
NICE
NICE
UGLY
NICE
NICE
NICE
UGLY
UGLY
UGLY
1 không phải tích của ít nhất một số nguyên tố; 2,3,5,7 là số nguyên tố; 6=2·3; 4=22, 8=23, 9=32, 10=2·5 không đẹp.
4
30
35
9699690
10000000000000000000
NICE
NICE
NICE
UGLY
30=2·3·5, 35=5·7, 9699690=2·3·5·7·11·13·17·19; 1019=219·519.

Bình luận

Không có bình luận tại thời điểm này.

gnatmake 12.2.0 a68g 3.1.2 nasm 2.16.1 as_x64 2.47 awk 1.3.4 gcc 16.2.0 dotnet 10.0.402 g++ 16.2.0 g++-themis 16.2.0 g++17 16.2.0 g++20 16.2.0 g++23 16.2.0 clang++ 22.1.8 dmd 2.113.0 dart 3.13.6 gforth 0.7.3 gfortran 15.3.0 go 1.27.3 groovyc 5.1.3 javac 26.0.2.1 node 26.12.1 julia 1.13.2 kotlinc 2.4.21 lean 4.35.0 sbcl 2.2.9 lua 5.5.1 nim 2.2.12 fpc 3.2.2 fpc-themis 3.2.2 perl 5.42.3 php 8.5.12 pike 8.0 swipl 9.0.4 pypy3 7.3.23 python3 3.15.1 racket 8.7 ruby 4.0.8 rustc 1.99.1 csc 5.3.0 ctoj-scratch 0.0.1 sed 4.9 swiftc 6.4.1 tclsh 8.6 bun 1.4.4 deno 2.9.8 v 0.5.2 zig 0.17.0