Trang chủ Tin Học Lớp 8 Nam rất yêu thích số nguyên tố vì vậy cậu...

Nam rất yêu thích số nguyên tố vì vậy cậu ta thường sưu tầm các số nguyên tố. Lần này bộ sưu tập của Nam là những số nguyên tố đặc biệt, tức là những số nguyên

Câu hỏi :

Nam rất yêu thích số nguyên tố vì vậy cậu ta thường sưu tầm các số nguyên tố. Lần này bộ sưu tập của Nam là những số nguyên tố đặc biệt, tức là những số nguyên tố đó có tổng các chữ số của nó lại là số nguyên tố. Yêu cầu: Hãy liệt kê ra tất cả các số nguyên tố đặc biệt nhỏ hơn hoặc bằng N theo thứ tự tăng dần. Dữ liệu vào: Từ tệp văn bản SPECPRIME.INP gồm 1 dòng chứa số N;       Kết quả: Ghi ra tệp văn bản SPECPRIME.OUT các số nguyên tố đặc biệt nhỏ hơn hoặc bằng N theo thứ tự tăng dần. Ví dụ: SPECPRIME.INP SPECPRIME.OUT 20 2 3 5 7 11

Lời giải 1 :

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í.

image

Thảo luận

-- https://hoidap247.com/cau-hoi/3259241
-- helpp

Lời giải 2 :

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.
        

Bạn có biết?

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ư

Tâm sự 8

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