K
Khách

Hãy nhập câu hỏi của bạn vào đây, nếu là tài khoản VIP, bạn sẽ được ưu tiên trả lời.

18 tháng 11 2025

Dưới đây là code C++ kiểm tra số nguyên tố bằng thuật toán Miller–Rabin (bản deterministic cho số 64-bit), dùng được an toàn cho mọi số nguyên 64-bit:

Miller–Rabin C++ (đầy đủ, chính xác cho 64-bit)



#include <bits/stdc++.h>
using namespace std;

using ull = unsigned long long;
using u128 = __uint128_t;

// Hàm nhân modular an toàn tránh tràn 64-bit
ull mul_mod(ull a, ull b, ull mod) {
    return (u128)a * b % mod;
}

// Hàm lũy thừa modular
ull pow_mod(ull a, ull d, ull mod) {
    ull result = 1;
    while (d) {
        if (d & 1) result = mul_mod(result, a, mod);
        a = mul_mod(a, a, mod);
        d >>= 1;
    }
    return result;
}

// Kiểm tra Miller-Rabin cho một cơ sở a
bool check_composite(ull n, ull a, ull d, int s) {
    ull x = pow_mod(a, d, n);
    if (x == 1 || x == n - 1) return false;

    for (int r = 1; r < s; r++) {
        x = mul_mod(x, x, n);
        if (x == n - 1) return false;
    }
    return true; // hợp số
}

// Miller–Rabin (deterministic cho 64-bit)
bool isPrime(ull n) {
    if (n < 2) return false;
    for (ull p : {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37})
        if (n % p == 0) return n == p;

    // Viết n−1 = d * 2^s
    ull d = n - 1;
    int s = 0;
    while ((d & 1) == 0) {
        d >>= 1;
        s++;
    }

    // Các cơ sở đảm bảo đúng với mọi n < 2^64
    for (ull a : {2ULL, 325ULL, 9375ULL, 28178ULL, 450775ULL, 9780504ULL, 1795265022ULL}) {
        if (a % n == 0) continue; 
        if (check_composite(n, a, d, s)) return false;
    }
    return true; // số nguyên tố
}

int main() {
    ull n;
    cout << "Nhap n: ";
    cin >> n;

    if (isPrime(n)) cout << n << " la so nguyen to\n";
    else cout << n << " khong phai so nguyen to\n";
}

🎯 Ưu điểm của đoạn code này

  • ✔ Không bị tràn số khi nhân (dùng __uint128_t)
  • ✔ Đảm bảo chính xác tuyệt đối cho mọi số 64-bit
  • ✔ Chạy rất nhanh, kiểm tra số hàng chục chữ số trong vài micro–giây
18 tháng 11 2025

ai lấy kí tự đặc biệt thì tham khảo vào đây

亗 ϟ 卍 ☯ ム ㋰ 〄 ﮩ٨ـﮩﮩ٨ـ♡ﮩ٨ـﮩﮩ٨ـ ╰‿╯ ×͜× ×͡× ┊ ×᷼× ☂ ´꒳` ౨ৎ ᶻ 𝗓 𐰁 .ᐟ ݁ ˖Ი𐑼⋆ ༗ 〆 ㊎

11 tháng 3 2022

#include <bits/stdc++.h>

using namespace std;

bool kt;

int n,i;

int main()

{

cin>>n;

kt=true;

for (i=2; i*i<=n; i++)

if (n%i==0) kt=false;

if ((kt==true) and (n>1)) cout<<"YES";

else cout<<"NO";

return 0;

}

 

18 tháng 7 2023

THAM KHẢO!

def is_prime(n):

 if n <= 1:

  return "KHÔNG"# Trường hợp n <= 1 không phải số nguyên tố

 elif n <= 3:

  return "CÓ"# Trường hợp n = 2 hoặc n = 3 là số nguyên tố

 elif n % 2 == 0:

  return "KHÔNG"# Trường hợp n chẵn lớn hơn

 
28 tháng 11 2019

Đáp án : C

Khí quyển nguyên thủy chưa có CO2 và O2

16 tháng 4 2017

Đáp án C

14 tháng 12 2019

Đáp án C

- Những khí được Miller và Urey sử dụng là CH4, NH3, H2 và hơi H2O. Hỗn hợp các khí này được đặt trong điều kiện phóng điện liên tục suốt một tuần → thu được các chất hữu cơ đơn giản trong đó có axit amin.

22 tháng 7 2015

647 là số nguyên tố

Mà bạn học lớp 6 hay chưa vậy nếu học lớp 6 rồi thì phải biết chớ

   Cuối sách lớp 6 tập 1 có bảng số nguyên tố nhỏ hơn 1000 đó

13 tháng 12 2020

uses crt;

var a:array[1..100]of integer;

i,n,t,kt,j:integer;

begin

clrscr;

write('Nhap n='); readln(n);

for i:=1 to n do

begin

write('A[',i,']='); readln(a[i]);

end;

writeln('Cac so vua nhap la: ');

for i:=1 to n do 

  write(a[i]:4);

writeln;

t:=0;

for i:=1 to n do 

  t:=t+a[i];

writeln('Tong cua day so la: ',t);

kt:=0;

for j:=2 to trunc(sqrt(t)) do 

  if t mod j=0 then 

    begin

kt:=1;

break;

end;

if kt=0 then writeln(t,' la so nguyen to')

else writeln(t,' khong la so nguyen to');

readln;

end.

13 tháng 12 2020

Cậu ơi sai khúc write('A[',i,']='); readln(a[i]); rồi nó cứ bị sao sao á

 

13 tháng 12 2020

uses crt;

var a:array[1..100]of integer;

i,n,t,kt:integer;

begin

clrscr;

write('Nhap n='); readln(n);

for i:=1 to n do

begin

write('A[',i,']='); readln(a[i]);

end;

writeln('Cac so ban vua nhap la: ');

for i:=1 to n do 

write(a[i]:4);

writeln;

t:=0;

for i:=1 to n do

t:=t+a[i];

writeln('Tong cac so vua nhap la: ',t);

if t>=2 then 

begin

kt:=0;

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

  if t mod i=0 then 

begin

kt:=1;

break;

end;

 if kt=0 then writeln(t,' la so nguyen to')

else writeln(t,' khong la so nguyen to');

end

else writeln(t,' khong la so nguyen to');

readln;

end.

25 tháng 1 2021

uses crt;

var a,x:longint;

{------------------ham-kiem-tra-so-nguyen-to---------------}

function ktnt(x:longint):boolean;

var kt:boolean;   

i:longint;

begin   

kt:=true;   

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

if x mod i=0 then       

begin           

kt:=false;           

break;       

end;   

if kt=true then ktnt:=true   

else ktnt:=false;

end;

{---------------chuong-trinh-chinh-------------------}

begin

clrscr;

repeat 

write('Nhap a='); readln(a);

until a>10;

if ktnt(a)=true then   

begin     

x:=a;     

repeat         

a:=a div 10;         

if ktnt(a)=true then a:=a div 10;     

until a<10;     

if (ktnt(a)=true) and (a>1) then writeln(x,' la so sieu nguyen to')     

else writeln(x,' khong la so sieu nguyen to');   

end

else writeln(a,' khong la so sieu nguyen to');

readln;

end.

bn ơi cấu hỏi hơi bị khó hiểu xíu