Bài này có thể tạo 1 function kiểm tra nguyên tố rồi xét chay từng số một từ 2 đến n, nhưng muốn để có thời gian chạy nhanh nhất thì ta cần sử dụng sàng eratosthenes, còn gọi là sàng nguyên tố để kiểm tra các số nguyên tố. Tư tưởng thuật toán:
- Tạo sàng nguyên tố bằng cách khởi tạo 1 mảng boolean với giá trị true. Nhân lên và đánh dấu tất cả các ô bội số của i thành false vì không phải là số nguyên tố. Tăng i đến khi số thứ i là số nguyên tố và lặp lại cho đến khi i>sqrt độ dài mảng. Lúc này ta được 1 mảng mà giá trị ô thứ i = true nếu i là số nguyên tố.
- Tạo 1 function tính tổng chữ số bằng cách div và mod cho 10 để lấy từng chữ số.
- Chạy 1 vòng for từ 2 đến n, tính tổng chữ số của i và xét trong mảng nguyên tố vừa tạo xem cả 2 có phải số nguyên tố không, nếu có thì in ra i.
Đây là code của mình. (raw: https://pastebin.com/YkUgHp5G)
Chúc bạn học tốt. Chọn đây là câu trả lời hay nhất nếu bạn thấy hợp lí.
uses crt;
type int = longint;
var
i, n, cnt: int;
pr, lpf, dp: array[0..1000000] of int;
procedure linear_sieve(n: int);
var i, j: int;
begin
for i:=2 to n do begin
if lpf[i] = 0 then begin
lpf[i]:=i;
inc(cnt); pr[cnt]:=i;
end;
for j:=1 to cnt do begin
if (pr[j] > lpf[i]) or (i * pr[j] > n) then break;
lpf[i * pr[j]]:=pr[j];
end;
end;
end;
procedure digit_sum(n: int);
var i: int;
begin
for i:=1 to n do begin
dp[i]:=dp[i mod 10] + (i mod 10);
end;
end;
function prime(n: int): boolean; begin exit(lpf[n] = n); end;
begin
clrscr;
readln(n);
linear_sieve(n);
digit_sum(n);
for i:=1 to n do
if prime(i) and prime(dp[i]) then write(i, ' ');
readln;
end.
Tin học, tiếng Anh: informatics, tiếng Pháp: informatique, là một ngành khoa học chuyên nghiên cứu quá trình tự động hóa việc tổ chức, lưu trữ, xử lý và truyền dẫn thông tin của một hệ thống máy tính cụ thể hoặc trừu tượng (ảo). Với cách hiểu hiện nay, tin học bao hàm tất cả các nghiên cứu và kỹ thuật có liên quan đến việc mô phỏng, biến đổi và tái tạo thông tin.
Nguồn : Wikipedia - Bách khoa toàn thưLớp 8 - Năm thứ ba ở cấp trung học cơ sở, học tập bắt đầu nặng dần, sang năm lại là năm cuối cấp áp lực lớn dần nhưng các em vẫn phải chú ý sức khỏe nhé!
Nguồn : ADMIN :))Copyright © 2021 HOCTAP247