trang chủ / bài tập / bearprime

Bear và số nguyên tố

Đề bài

Mô tả

Đây là một bài toán tương tác (interactive).

Hệ thống đã chọn một số nguyên bí mật X với 2X100. Nhiệm vụ của bạn là xác định Xsố nguyên tố hay hợp số.

Số nguyên X>1 được gọi là số nguyên tố nếu nó có đúng hai ước số phân biệt là 1X. Nếu X>1 không phải số nguyên tố thì nó là hợp số.

Bạn được phép đặt tối đa 20 truy vấn. Trong mỗi truy vấn, bạn in ra một số nguyên q với 2q100. Hệ thống trả lời:

  • yes nếu q là ước của X;
  • no nếu q không phải ước của X.

Khi đã sẵn sàng, bạn in ra prime nếu cho rằng X là số nguyên tố, hoặc composite nếu cho rằng X là hợp số, rồi kết thúc chương trình.

Bạn sẽ nhận kết quả sai nếu đặt quá 20 truy vấn, in ra số nằm ngoài đoạn [2,100], hoặc đưa ra kết luận sai.

Dữ liệu vào

Sau mỗi truy vấn, đọc một dòng chứa xâu yes hoặc no — câu trả lời cho truy vấn vừa in.

Dữ liệu ra

Mỗi truy vấn in trên một dòng: một số nguyên q với 2q100.

Khi kết thúc, in ra prime hoặc composite trên một dòng.

Sau mỗi lần in, bạn phải flush output (ví dụ cout.flush() trong C++, flush=True trong Python).

Ràng buộc

  • 2X100
  • Tối đa 20 truy vấn

Ví dụ

Input Output Giải thích

yes
no
yes
2
80
5
composite
Số bí mật là 30. Nó chia hết cho cả 25 nên có ít nhất hai ước nguyên tố phân biệt, suy ra là hợp số.

no
yes
no
no
no
58
59
78
78
2
prime
Số bí mật là 59. Vì 59 là số nguyên tố nên chỉ có chính nó là ước trong [2,100], mọi truy vấn khác đều trả lời no.

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.46 awk 1.3.4 gcc 16.1.0 csc 6.12.0.200 g++ 16.1.0 g++-themis 16.1.0 g++17 16.1.0 g++20 16.1.0 g++23 16.1.0 clang++ 22.1.6 dmd 2.112.0 dart 3.12.1 gforth 0.7.3 gfortran 12.2.0 GO groovyc 5.0.6 javac 25.0.3 node 26.2.0 kotlinc 2.3.21 sbcl 2.2.9 lua 5.4.8 nim 2.2.10 fpc 3.2.2 fpc-themis 3.2.2 perl 5.36.0 php 8.5.6 pike 8.0 pypy3 7.3.23 python3 3.14.5 racket 8.7 ruby 4.0.5 rustc 1.96.0 csc 5.3.0 ctoj-scratch 0.0.1 sed 4.9 tclsh 8.6 bun 1.3.14 deno 2.8.1 v 0.5.1 zig 0.16.0