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 ai <= 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 |
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.
