Tình huống lạ trong mã kiểm tra số nguyên

Question

Khi tôi đang giải quyết vấn đề cho Project Euler, nó yêu cầu tôi tổng hợp tất cả các số nguyên tố dưới 2 triệu. Đây là mã của tôi:

#include<stdio.h> 
#include<math.h> 
int isPrime(int); 
int main() { 
    long long int sum = 0; 
    int i; // index 
    for(i = 2 ; i < 2000000 ; i++) { 
     if(isPrime(i)) { 
      sum += i; 
     } 
    } 
    printf("%lli\n", sum); 
} 

int isPrime(int num) { 
    int i; // index 
    int sq = sqrt(num); 
    for(i = 2 ; i <= sq ; i++) { 
     if(num % i == 0) { 
      return 0; 
     } 
    } 
    return 1; 
} 

Mã này dẫn đến câu trả lời đúng, 142913828922. Nhưng khi tôi thay đổi vòng lặp for trong isPrime() tới:

for(i = 2; i <= sq+1; i++) // or even sq+2, sq+3, etc. 

Nó dẫn đến kết quả không chính xác như 142.913.828.920 và 142913828917, v.v.

Tại sao lỗi này xảy ra? Về mặt lý thuyết, nó không thay đổi số isPrime() gửi đến main(), phải không?

Answer 1

Xem xét bạn đã thay đổi tổng số từ 142913828922 thành 142913828920, thì sự khác biệt là 2, có nghĩa là bạn đang giải thích 2 không phải là số nguyên tố. Thay đổi sq thành sq+1 sẽ đạt được sự khác biệt đó. Thay đổi nó thành sq+2 sẽ kết thúc làm cho 3 không phải là số nguyên tố.

((int)sqrt(2))+1 == 2 
((int)sqrt(3))+2 == 3 

v.v.

Answer 2

nếu bạn thay đổi vòng lặp để

for(i = 2 ; i <= sq+1 ; i++) 

sau đó 2 không còn được coi là đắc địa, bởi vì bạn kiểm tra nếu 2 % 2 == 0.

Tương tự cho số lớn hơn bạn thêm, ngày càng nhiều số nguyên tố sẽ không được phát hiện như vậy.

Answer 3

Nó là tốt hơn để sử dụng

for(i = 2 ; i*i <= num ; i++) { 
    if(num % i == 0) { 
     return 0; 
    } 
} 

Thay vì

int sq = sqrt(num); 
for(i = 2 ; i <= sq ; i++) { 
    if(num % i == 0) { 
     return 0; 
    } 
} 

để tránh vấn đề này với chức năng sqrt