Tìm số nguyên tố

[Master_Baby]

Một bài toán đơn giản khi mới học lập trình là tìm số nguyên tố trong 1 khoảng cho trước, thường là [2..n]. Nhưng cũng thường người ta xét một số nguyên tố là số không chia hết cho các số từ 2 -> round(căn n). Tóm lại, điều em muốn hỏi các đại ca là phương pháp tìm số nguyên tố tối ưu nhất nhất (không phải phương pháp trên rùi,....)?

[anhtuanvuong]

Một bài toán đơn giản khi mới học lập trình là tìm số nguyên tố trong 1 khoảng cho trước, thường là [2..n]. Nhưng cũng thường người ta xét một số nguyên tố là số không chia hết cho các số từ 2 -> round(căn n). Tóm lại, điều em muốn hỏi các đại ca là phương pháp tìm số nguyên tố tối ưu nhất nhất (không phải phương pháp trên rùi,....)?

Anh thấy thuật toán xét từ 2->căn n là chuẩn nhất rùi hay sao ý.Anh có lên google search nhưng cũng chi thấy thía thui em ah.Tất nhiên không phải số nào cũng xét từ 2->căn n.

Anh thấy thuật toán xét từ 2->căn n là chuẩn nhất rùi hay sao ý.Anh có lên google search nhưng cũng chi thấy thía thui em ah.Tất nhiên không phải số nào cũng xét từ 2->căn n.

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <assert.h>

typedef unsigned long long bignum;

void printPrime(bignum bn)
{
static char buf[1000];

sprintf(buf, "%ull", bn);
buf[strlen(buf) - 2] = '\0';
printf("%s\n", buf);
}

void findPrimes(bignum topCandidate)
{
bignum candidate = 2;
while(candidate <= topCandidate)
{
bignum trialDivisor = 2;
int prime = 1;
while(trialDivisor * trialDivisor <= candidate)
{
if(candidate % trialDivisor == 0)
{
prime = 0;
break;
}
trialDivisor++;
}
if(prime) printPrime(candidate);
candidate++;
}
}

int main(int argc, char *argv[])
{
bignum topCandidate = 1000;
if(argc > 1)
topCandidate = atoll(argv[1]);
findPrimes(topCandidate);
return 0;
}

[Rikku]

Theo mình biết thì có :
+ Cách xét từ 2 -> sqrt(n). Nhưng mà chúng ta cải tiến chút xíu, thay vì việc tăng từng đơn vị rồi chia,ta tăng 2 rùi 4 rùi 2... mỗi lần như thế lại chia xem có dư ko. VD:5->7->11->13->17->19->23....
Chạy nhanh khoảng gấp 3 lần so với việc xét từng số 1.

+Dùng phuơng pháp xác suất MillerTest:
Thuật toán xác xuất tiếp cận bài toán theo hướng khác, không theo con đường tìm một ước không tầm thường mà dựa vào hai tính chất khác của số nguyên tố. Cho p là một số nguyên tố, a là số nguyên không chia hết cho p, ta có :
a^(p-1) = 1 (mod p) (1)
a^2 = 1 (mod p) <-> a = 1 (mod p) hoặc a = -1 (mod p). (2).

Giả sử p-1 = q.2^t trong đó q là một số nguyên dương lẻ. Theo (1) và (2), với mọi số a không chia hết cho p ta đều có :
+ a^(q) = 1 (mod p) hoặc
+ a^(q.2^r) = -1(mod p) với một số nguyên r nào đó thoả 0 <= r < t. (*)

Như vậy, một số n là nguyên tố thì nó phải thoả mãn điều kiện trên với mọi 1 <= a <= n-1, ngược lại nếu tồn tại một a không thoả mãn tính chất trên thì chắc chắn n không phải là số nguyên tố. Mặt khác, ta có thể chứng minh được rằng, nếu n là một hợp số lẻ > 3 thì có không quá (n-1) / 4 giá trị a trong khoảng 1 đến n-1 thoả mãn (*). Do đó, với một số a chọn ngẫu nhiên trong khoảng 1 đến n-1, thì xác suất a thoả mãn (*) không quá 1/4 , và nếu k lần chọn thì xác suất để mọi lần chọn đều thoả mãn là không quá 1/(4^k).
Đây là code
Giải thích hộc máu mất

Function Prime(n : Integer) : Boolean;
Var
  i, a : Integer;
Begin
Prime := False;
Cal(n, q, t)              {phân tích n-1 = q.2^t}     
For i := 1 to k do 
Begin
  a := Random(n-1) + 1;
  if MillerTest(n, a, q, t) = False then Exit;
End;
Prime := True;
End;

Function Power(a, q, n : Integer) : Integer;
Var
  c, p2, u : Integer;
Begin
c := 1;
u := a;
p2 := 1;
repeat
if q and p2 <> 0 then c := (c * u) mod n;
  p2 := p2 shl 1;
u := (u * u) mod n;
until p2 > q;
Power := c;
End;

Function MillerTest(n, a, q, t : Integer) : Boolean;
Var
pre, c, i, j : Integer;
Begin
c := Power(a, q, n);
pre := n-1;
for i := 0 to t do 
begin
if c = 1 then 
begin
MillerTest := (pre = n-1);
Exit;
end;
pre := c;
c := (c * c) mod n;
end;
MillerTest := False;
End;

Thuật toán thực hiện k lần kiểm tra có chi phí cỡ O(k(logn)^3), xác suất sai không quá 1/4^k . Độ phức tạp của thuật toán tăng tuyến tính theo k, xác suất sai lầm giảm theo hàm mũ với k. Chỉ cần chọn k không quá lớn (k > 30) thì xác suất sai lầm quá nhỏ, do đó nếu n trải qua phép thử với k cơ sở a chọn ngẫu nhiên thì có thể khẳng định gần như chắc chắn n là số nguyên tố.

--------------

Err..còn cái nào nữa ko nhỉ ?

[Master_Baby]

- Thân gửi mọi người :
Liệu dùng kiểu sàng số ngtố của.... ai đó... được không nhỉ? Loại bỏ tất cả các số nằm trong khoảng [2..n] chia hết cho 1 số cho trước < n......
- Thân
P/s: anhtuanvuong có wen em ko vậy?

[mtt333]

- Thân gửi mọi người :
Liệu dùng kiểu sàng số ngtố của.... ai đó... được không nhỉ? Loại bỏ tất cả các số nằm trong khoảng [2..n] chia hết cho 1 số cho trước < n......
- Thân
P/s: anhtuanvuong có wen em ko vậy?

Tất nhiên là sàng vẫn được nhưng nếu cần tìm một số nguyên tố lớn thì chạy sẽ rất lâu.
Số nguyên tố lớn có ứng dụng lớn trong bảo mật, khi đó không ai có thời gian ngồi đợi chú chạy, chia và tìm.

[Hermex]

Để tìm số nguyên tố bạn có thể dựa vào định lý sau :
Nếu n = 2 * r * q + 1 , q - là số nguyên tố , r <= 2*q + 1, nếu với a là số tự nhiên thỏa mãn :
a^ ( n-1) = 1 ( mod n ) và a^(2*r) != 1 ( mod n ) thì n là nguyên tố .

[Master_Baby]

Anh ui, cho em hỏi đoạn " 1 (mod n) " là sao? nếu là 1 mod n => kết quả là n muh???

[bete]

Thân gửi MasterBaby

Anh ui, cho em hỏi đoạn " 1 (mod n) " là sao?

Xin trả lời thay cho Hermex:

Viết: a = b (mod n)
có nghĩa là: a mod n = b mod n (số dư khi chia a cho n bằng số dư khi chia b cho n).

Nếu b < n thì cũng hiểu được là: a mod n = b

-thân

[DoQuocDuy]

Có rất nhiều thuật toán để xác định một số có phải là số nguyên tố hay không. 8/2002 lịch sử chứng kiến một thành công bất ngờ khi nhà tin học người Ấn Độ Manindra Agrawal cùng với 2 sinh viên của mình là Neeja Kayal và Nitin Saxena đã tìm ra một thuật toán chỉ dài 13 dòng cho phép xác định tính chắc chắn của ~ số rất lớn (có tới hàng trăm chữ số). Điều này đã làm rất nhiều nhà toán học trên thế giới nghi ngờ tính đúng đắn của thuật toán và họ đã lao vào kiểm tra sự chính xác của nó và cho tới nay vẫn chưa ai tìm thấy sự nhầm lẫn nào. Tất cả đều phải thốt lên rằng " Thật là thần diệu, mà sao không có ai tìm ra được thuật toán này sớm hơn!". Thuật toán này bắt nguồn từ định lý nhỏ Fecma đấy các bạn ạ: Nếu p là số nguyên tố thì a^p = a (mod p), với a thuộc tập N. (dấu = ở đây hiều là "đồng dư"). (Định lý lớn Fecma cũng đã được chứng minh rồi x^n + y^n = Z^n).
Và sau đây là thuật toán:

Input: integer n > 1
1. if(n is of the form  a^b, b>1)
   output COMPOSITE;
2. r = 2;
3. while(r<n) {
4. if(gcd(n,r)<>1) output COMPOSITE;
5. if(r is prime)
6. let q be the largest prime factor of r-1;
7. if(q>=sqrt(r)*log(n)) and (n^[(r-1)/q] <> 1(mod r))
8. break;
9. r <- r + 1;
10. }
11. for a = 1 to 2*sqrt(r)log(n)
12. if((x-a)^n <> (x^n - a)(mod n, x^r - 1))
     output COMPOSITE;
14. output PRIME;

[amida]

Tôi nghĩ cách này là dễ nhất rồi, chuẩn nhất để tìm số ngtố nữa

program snt;
uses CRT;
var
n,k,i:integer;
 begin
   k:= 100 {Có thể thay đổi cho phù hợp}
   write('Nhap 1 so: ');
   if(n<k) then
     begin
       i:=2;
       while(n mod i>0) do
       i:=i+1;
       if(i = n) then writeln(n,' la so nguyen to')
       else writeln(n,' ko la so ngto');
     end
    else writeln(n,' ko la so ngto');
   readln;
 End.