C++ Thủ số nhiệm vụ từ cuốn sách

Question

Tôi là một người mới bắt đầu C++;) Làm thế nào tốt là mã dưới đây như một cách để tìm tất cả các số nguyên tố giữa 2-1000:

int i, j; 

for (i=2; i<1000; i++) { 
    for (j=2; j<=(i/j); j++) { 
    if (! (i%j)) 
     break; 
    if (j > (i/j)) 
     cout << i << " is prime\n"; 
    } 
} 

Answer 1

Câu trả lời đơn giản cho toàn bộ chuỗi văn bản mà chúng tôi đăng lên ở đây là: Phòng thử nghiệm! Nếu ai đó đề cập cơ sở toán học rằng nhiệm vụ này được dựa trên, chúng tôi tiết kiệm rất nhiều thời gian;)

Answer 2

Bạn dừng lại khi j = tôi. Việc tối ưu hóa đơn giản đầu tiên là dừng khi j = sqrt (i) (vì không có yếu tố nào lớn hơn số căn bậc hai của nó).

Triển khai nhanh hơn nhiều, ví dụ: sieve of eratosthenes.

Chỉnh sửa: mã có vẻ hơi bí ẩn, vì vậy đây là cách hoạt động:

Điều kiện chấm dứt vào bên trong là i/j, tương đương với j<i (đó là rõ ràng hơn nhiều), kể từ khi cuối cùng đã có j==i, chúng tôi sẽ có i/j==0 và cho sẽ phá vỡ.

Séc tiếp theo if(j>(i/j)) thực sự khó chịu. Về cơ bản, nó chỉ kiểm tra xem vòng lặp có đạt đến điều kiện cuối của for hay không (nếu chúng ta có một số nguyên tố) hoặc nếu chúng ta nhấn ngắt rõ ràng (không có số nguyên tố). Nếu chúng ta nhấn vào cuối của, thì j==i+1 (suy nghĩ về nó) =>i/j==0 => nó là một nguyên tố. Nếu chúng ta phá vỡ, nó có nghĩa là j là một yếu tố của i, nhưng không chỉ là bất kỳ yếu tố nào, nhỏ nhất trong thực tế (vì chúng ta thoát ra ở j đầu tiên chia i)! Vì j là yếu tố nhỏ nhất, yếu tố khác (hoặc sản phẩm của các yếu tố còn lại, được đưa ra bởi i/j) sẽ lớn hơn hoặc bằng j, do đó thử nghiệm. Nếu j<=i/j, chúng tôi sẽ nghỉ ngơi và j là hệ số nhỏ nhất là i.

Đó là một số mã không đọc được!

Answer 3

Không tốt lắm. Theo quan điểm khiêm nhường của tôi, sự thụt đầu dòng và khoảng cách là ghê tởm (không có hành vi phạm tội). Để làm sạch nó lên một số:

int i, j; 

for (i=2; i<1000; i++) { 
    for (j=2; i/j; j++) { 
     if (!(i % j)) 
      break; 
     if (j > i/j) 
      cout << i << " is prime\n"; 
    } 
} 

này cho thấy một lỗi: các if (j > i/j) ... nhu cầu để được vào bên ngoài của vòng lặp bên trong để làm việc này. Ngoài ra, tôi nghĩ rằng điều kiện i/j là khó hiểu hơn (chưa kể đến chậm hơn) chỉ cần nói j < i (hoặc thậm chí không có gì, bởi vì một lần j đạt đến i, i % j sẽ là 0). Sau những thay đổi này, chúng tôi có:

int i, j; 

for (i=2; i<1000; i++) { 
    for (j=2; j < i; j++) { 
     if (!(i % j)) 
      break; 
    } 
    if (j > i/j) 
     cout << i << " is prime\n"; 
} 

Tác phẩm này hoạt động. Tuy nhiên, số j > i/j gây nhầm lẫn cho tôi. Tôi thậm chí không thể tìm ra lý do tại sao nó hoạt động (tôi cho rằng tôi có thể hình dung ra nếu tôi dành một thời gian looking like this guy). Tôi sẽ viết if (j == i) để thay thế.

Những gì bạn đã triển khai ở đây được gọi là trial division. Một thuật toán tốt hơn là Sieve of Eratosthenes, như được đăng trong một câu trả lời khác. Một vài điều cần kiểm tra xem bạn có triển khai Sieve of Eratosthenes không:

1. Nó sẽ hoạt động.
2. Không nên sử dụng phân chia hoặc mô đun. Không phải là chúng "xấu" (được cấp, chúng có xu hướng chậm hơn so với cộng, trừ, phủ định, vv), nhưng chúng không cần thiết, và nếu chúng có mặt, nó có thể có nghĩa là triển khai isn không thực sự hiệu quả.
3. Nó sẽ có thể tính toán số nguyên tố nhỏ hơn 10.000.000 trong khoảng một giây (tùy thuộc vào phần cứng, trình biên dịch, v.v.) của bạn.

Answer 4

Trước hết, mã của bạn vừa ngắn vừa chính xác, rất tốt cho người mới bắt đầu. ;-)

Đây là những gì tôi sẽ làm gì để cải thiện mã:

1) Xác định các biến bên trong các vòng, vì vậy họ không bị lẫn lộn với cái gì khác. Tôi cũng sẽ làm cho một tham số bị ràng buộc hoặc một hằng số.

#define MAX 1000 
for(int i=2;i<MAX;i++){ 
    for(int j=2;j<i/j;j++){ 
     if(!(i%j)) break; 
     if(j>(i/j)) cout<<i<<" is prime\n"; 
    } 
} 

2) Tôi sẽ sử dụng số Sieve of Eratosthenes, như Joey Adams và Mau đã đề xuất. Lưu ý cách tôi không phải viết giới hạn hai lần, vì vậy hai tập quán sẽ luôn giống nhau.

#define MAX 1000 
bool prime[MAX]; 
memset(prime, sizeof(prime), true); 
for(int i=4;i<MAX;i+=2) prime[i] = false; 
prime[1] = false; 
cout<<2<<" is prime\n"; 
for(int i=3;i*i<MAX;i+=2) 
    if (prime[i]) { 
     cout<<i<<" is prime\n"; 
     for(int j=i*i;j<MAX;j+=i) 
      prime[j] = false; 
    } 

Các giới hạn cũng đáng chú ý. i*i<MAX nhanh hơn rất nhiều so với j > i/j và bạn cũng không cần đánh dấu bất kỳ số nào < i * i, bởi vì chúng đã được đánh dấu, nếu chúng là hỗn hợp. Điều quan trọng nhất là time complexity.

3) Nếu bạn thực sự muốn thực hiện thuật toán này nhanh, bạn cần phải tối ưu hóa bộ nhớ cache. Ý tưởng đầu tiên là tìm tất cả các số nguyên tố < sqrt (MAX) và sau đó sử dụng chúng để tìm phần còn lại của số nguyên tố . Sau đó, bạn có thể sử dụng cùng một khối bộ nhớ để tìm tất cả các số nguyên tố từ 1024-2047, giả sử, và sau đó là 2048-3071. Điều này có nghĩa là mọi thứ sẽ được giữ trong L1-cache. Tôi đã từng đo tốc độ tăng tốc ~ 12 lần bằng cách sử dụng tối ưu hóa này trên Sàng Eratosthenes.

Bạn cũng có thể cắt giảm không gian sử dụng một nửa bằng cách không lưu số chẵn, có nghĩa là bạn không phải thực hiện các tính toán để bắt đầu làm việc trên khối mới thường xuyên.

Nếu bạn là người mới bắt đầu, có lẽ bạn nên quên bộ nhớ cache trong giây lát.

Answer 5

#include <stdio.h> 
#define N 1000 

int main() 
{ 

    bool primes[N]; 
    for(int i = 0 ; i < N ; i++) primes[i] = false; 
    primes[2] = true; 

    for(int i = 3 ; i < N ; i+=2) { // Check only odd integers  
     bool isPrime = true;  
     for(int j = i/2 ; j > 2 ; j-=2) { // Check only from largest possible multiple of current number 
      if (j%2 == 0) { j = j-1; } // Check only with previous odd divisors 
      if(!primes[j]) continue;  // Check only with previous prime divisors 
      if (i % j == 0) {    
       isPrime = false; 
       break; 
      } 
     } 
     primes[i] = isPrime; 
    } 

    return 0; 
} 

này đang làm việc mã. Tôi cũng bao gồm nhiều tối ưu hóa được đề cập bởi các áp phích trước đó. Nếu có bất kỳ tối ưu hóa khác có thể được thực hiện, nó sẽ được thông tin để biết.

Answer 6

Chức năng này hiệu quả hơn để xem liệu số có phải là số nguyên tố hay không.

bool isprime(const unsigned long n) 
{ 
if (n<2) return false; 
if (n<4) return true; 
if (n%2==0) return false; 
if (n%3==0) return false; 
unsigned long r = (unsigned long) sqrt(n); 
r++; 
for(unsigned long c=6; c<=r; c+=6) 
{ 
    if (n%(c-1)==0) return false; 
    if (n%(c+1)==0) return false; 
}