Phương pháp tối ưu để tìm số nguyên tố

[Hung_Dang1 (Hưng Đặng)]

Đây là 1 phương pháp tìm số nguyên tố của e. e Tự nghĩ chạy thử rồi mới tham khảo các nơi khác… HÃY CÙNG THẢO LUẬN VÀ CMT VỀ NHỮNG PHƯƠNG PHÁP HAY MÀ MN THẤY LÀ TỐT NHẤT.
Cảm ơn. dưới đây là code của e.

#inlucde <stdio.h>
int main(void){
    int i, n = 0;
    printf("n =");
    scanf("%d[^\n]", &n);
    for (i = 2; i< n - 1; i++){
         if(( n % i) == 0){
             printf("n khong phai la so nguyen to.\n"); 
             break;
        }
    }
    printf("n la so nguyen to.");
    return 0;
}

[dtran]

break;

return;

i< n - 1

cái này chỉ cần i <= sqrt(n) sẽ tối ưu hơn nhé

[hungaya (Hung)]

Chạy trâu rồi lưu vào file sau này xài lại.
Lần sau chỉ cần binary search trên đống số nguyên tố tìm được.

[rogp10]

Bạn vui lòng tìm kiếm trước khi post nhé

[Wiki] Hàm Kiểm Tra số nguyên tố trong C/C++

Mình thì thường dùng cách này thôi, không tối ưu mấy bool soNguyenTo(int soA) { soA=abs(soA); if (!soA) return false; if (soA>=3 && !(soA%2)) return false; for (int i=3; i<=sqrt(soA); i+=2) if (!(soA%i)) return false; return true; }

Sàng nguyên tố và một số ứng dụng

Thiếu segmented sieve khắc phục được nhược điểm sử dụng quá nhiều mem bằng cách chỉ sử dụng một vùng nhớ nhỏ hơn kích thước của mem (OS) page và tốc độ cũng cao hơn. Đầu tiên ta có tổng 1 + 1/2 + 1/3 + 1/5 + 1/7 + … + 1/lastprime(n) = 1 + O(loglog(n)) https://arxiv.org/abs/math/0504289 . Với phiên bản đầy đủ dễ thấy tổng số lần đánh dấu là n(1 + 1/2 + 1/3 + 1/5 + …), hay đpt là n*O(loglogn) với tất cả các thao tác đều là O(1). Phần trừ ra có sai số rất lớn nên rất vô nghĩa. =…

Bài toán liệt kê số nguyên tố nhỏ hơn n trong c

Đã sửa lại cho bạn nè, đã tối ưu hóa thuật toán để không phải lặp nhiều. #include <stdio.h> #include <math.h> int nguyento(int n) { int i; for (i = 2; i <= (int)sqrt(n); i++) if (n % i == 0 and n != i) { return 1; break; } } int main(void) { int i, n, kt; printf("Nhap vao so nguyen n: "); scanf("%d", &n); printf("\nCac so nguyen to nho hon n la: "); for (i = 2; i <= n; i++) if (nguyento(i) != 1) prin…

Cách phân tích một số thành thừa số nguyên tố nhanh

Mình giải thích ý 2 trước: Do nếu i chia hết n thì n/i chia hết n, nên ta thu được một cặp có số lớn số bé. Vậy khi i <= n/i thì i^2 <= n. Ý 1: Sau bước lặp i=j, n không chia hết cho j (nếu có thì vẫn còn trong vòng while bên trong). Vậy theo quy nạp, n không chia hết cho 2…j, vậy nếu j+1 chia hết n thì j+1 không thể chia hết cho bất cứ số nào trong [2…j] được nữa (nếu có thì hóa ra là chưa chia cho hết?), theo định nghĩa của số nguyên tố Thực ra từ j (lẻ) có thể nhảy lên j+2 (c…

Sàng Eratosthenes số nguyên tố trong mảng một chiều

Đã dùng Fermat thì sao không dùng Rabin-Miller? Số Carmichael có thể ăn được hết test Fermat, nhưng sẽ không ăn được hết RM => RM tốt hơn. RM khác hai chỗ: Bước nhân mũ bt bằng +/-1 là xong. Bước bình phương: nếu gặp -1 là số nguyên tố (vì x^2 = 1 mod số nguyên tố chỉ có hai nghiệm +/-1) (xem note, bđ Euclid) còn khác -1 mà bay lên 1, nghĩa là không phải. Vì như vậy là x^2 = 1 (mod p) có nghiệm khác -1 Test RM thực ra vẫn là a^(n-1) ?=? 1 (mod n), nhưng logic chi tiết hơn. Chia thử số n. T…

Số nguyên tố có giá trị không lớn hơn N

Ôn lại định nghĩa: Hợp số là tích của hai số tự nhiên lớn hơn 1 (n = a * b). Số nguyên tố là số có đúng hai ước 1 và chính nó. Số 1 đứng ngoài cả hai tập và nó là một phần tử đơn vị (bạn nào học Số học ở ĐH rồi sẽ hiểu). Ta nói rằng hợp số và số nguyên tố là một phân hoạch của N* \ {1}. Khi viết n = a*b thì (a, b) là một cặp và luôn có a <= sqrt(n) <= b, vì nếu a < b < sqrt(n) thì ab < n, còn b > a > sqrt(n) thì ab > n. Vậy chạy từ 2 đến sqrt(n) là xong. Thuật toán như sau: : Inpu…

[Hung_Dang1 (Hưng Đặng)]

cái này chỉ cần i <= sqrt(n) sẽ tối ưu hơn nhé

à đúng rồi… em quên mất… vì chỉ cần loop đến 1 nửa giá trị của n là đủ.
với số bé thì ổn còn số lớn thì cả 1 vấn đề. cảm ơn bác…

return;

em muốn thoát luôn bác à… dù exit cũng được ạ…

[rogp10]

Đọc file là lâu nhất thua mỗi curl thôi.