Làm cách nào để tăng tốc chương trình này?

Question

Tôi hiện đang cố gắng giải quyết ProjectEuler problem và tôi đã gỡ mọi thứ, ngoại trừ tốc độ. Tôi gần như chắc chắn lý do chương trình thực hiện rất chậm là do các vòng lồng nhau. Tôi rất thích một số lời khuyên về cách tăng tốc độ này. Tôi là một lập trình viên mới, vì vậy tôi không quen thuộc với nhiều phương pháp/chủ đề nâng cao hơn.

public class Problem12 { 

    public static void main(String[] args) { 
     int num; 

     for (int i = 1; i < 15000; i++) { 
      num = i * (i + 1)/2; 
      int counter = 0; 

      for (int x = 1; x <= num; x++) { 
       if (num % x == 0) { 
        counter++; 
       } 
      } 
      System.out.println("[" + i + "] - " + num + " is divisible by " + counter + " numbers."); 
     } 
    } 
} 

EDIT: Dưới đây là mã mới nhanh hơn theo cấp số nhân. Loại bỏ các dòng in liên tục cũng như để tăng tốc độ nó lên nhiều hơn.

public class Problem12 { 

    public static void main(String[] args) { 
     int num; 

     outerloop: 
     for (int i = 1; i < 25000; i++) { 
      num = i * (i + 1)/2; 
      int counter = 0; 

      double root = Math.sqrt(num); 
      for (int x = 1; x < root; x++) { 
       if (num % x == 0) { 
        counter += 2; 
        if (counter >= 500) { 
         System.out.println("[" + i + "] - " + num + " is divisible by " + counter + " numbers."); 
         break outerloop; 
        } 
       } 
      } 
     } 
    } 
} 

Answer 1

Đối với người mới bắt đầu, khi nhìn vào ước, bạn không bao giờ cần phải đi xa hơn so với căn bậc hai của số lượng, bởi vì mỗi ước dưới căn bậc hai có tương đương ở trên.

n = a * b => a <= sqrt(n) or b <= sqrt(n) 

Sau đó, bạn cần phải đếm phía bên kia của bộ phận:

double root = Math.sqrt(num); 
for (int x = 1; x < root; x++) { 
    if (num % x == 0) { 
     counter += 2; 
    } 
} 

Các căn bậc hai là đặc biệt bởi vì nó chỉ tính một lần nếu nó là số nguyên:

if ((double) ((int) root) == root) { 
    counter += 1; 
} 

Answer 2

Bạn chỉ cần phải xác định số lượng. p^a * q^b * r^c có (a+1)*(b+1)*(c+1) ước. Dưới đây là một số triển khai cơ bản sử dụng ý tưởng này:

static int Divisors(int num) { 
    if (num == 1) { 
     return 1; 
    } 

    int root = (int) Math.sqrt(num); 
    for (int x = 2; x <= root; x++) { 
     if (num % x == 0) { 
      int c = 0; 
      do { 
       ++c; 
       num /= x; 
      } while (num % x == 0); 
      return (c + 1) * Divisors(num); 
     } 
    } 

    return 2; 
} 

public static void test500() { 
    int i = 1, num = 1; 
    while (Divisors(num) <= 500) { 
     num += ++i; 
    } 

    System.out.println("\nFound: [" + i + "] - " + num); 
}