Question

[Nhung]

FUTURE - Số tương lai Dữ liệu vào: standard input Dữ liệu ra: standard output Giới hạn thời gian: 1.0 giây Giới hạn bộ nhớ: 512 megabyte Đăng bởi: kid2201

Số “tương lai” là số có các ước (không kể 1 và chính nó) là các số nguyên tố. VD: số 10 có ước là 2 và 5 là các số nguyên tố nên 10 là số “tương lai”.

Yêu cầu: Cho dãy số nguyên (a1, a2, ..., an), 1 <= n <= 1000; với mọi i sao cho a_i <= 10^6. Hãy cho biết trong dãy trên có bao nhiêu số tương lai.

Dữ liệu vào: Đọc từ file văn bản FUTURE.INP có cấu trúc như sau:

Dòng thứ nhất chứa số nguyên dương n.

Dòng thứ hai chứa n số nguyên a1, a2, ..., an.

Dữ liệu ra: Ghi ra file văn bản FUTURE.OUT ghi một số nguyên dương là số lượng các số tương lai. Các số trong file dữ liệu cách nhau ít nhất 1 dấu cách

Ví dụ

FUTURE.INP	FUTURE.OUT
9 9 7 10 6 17 4 19 21 13	5

Answer 1

[Nguyễn Thái Hưng]

program FUTURE;

var n,dem:int64;

a:array[1..1000000] of int64;

i,j:longint;

kt:boolean; 

function KTSNT(n:int64):boolean;

var i:longint;

kt:boolean;

begin

if n < 2 then KTSNT := false 

else begin  

kt := true; 

for i:= 2 to trunc(sqrt(n)) do  

if n mod i = 0 then  

begin  

kt := false; 

break; 

end; 

if kt = true then KTSNT := true 

else KTSNT := false; 

end;

end; 

BEGIN 

readln(n);

for i := 1 to n do read(a[i]);

dem := 0;

for i := 1 to n do 

begin

 if KTSNT(a[i]) then continue

else if a[i] = 1 then continue

else 

begin 

kt := true;

for j := 2 to a[i]-1 do 

if a[i] mod j = 0 then 

if KTSNT(j) = false then 

begin 

kt := false;

break;

end;

end;

if kt = true then inc(dem);

end;

write(dem);

END.