Arthur와 co prime 프로그램 Coprime Conundrum이 원하는 출력을 얻지 못했습니다.

Question

하나의 Java 프로그램을 작성하고 있습니다. 아서 (p,q) 쌍의 수이 될 수있는 기능 f(k)를 정의하도록 :

• 1< p <= q <= k
• p와 q는 coprimes은 내가 하나 개 프로그램을 작성하기로하고

PQ = K이다 주어진 정수 n 그리고 아더가 그 결과를 찾아서 인쇄하도록 도와주세요 (Σ k=1 to n) f(k)

Constrai 국세청 : 예를 들어 1<=n<=pow(10,9)

(입력) 그래서 f(6) = 1
k=10를 들어 유효 하나가,의 하나의 유효한 쌍 (2,3)이 k=6를 들어 1<=k<=12
에 대한 f(k)의 값에 대해 n = 12
을 가정 해 봅시다 쌍 (2,5)이므로 f(10) = 1
k=12의 경우 유효한 쌍이 하나 있습니다. (3,4),

import java.util.Scanner; 
class ArthurFunction{ 
    public static boolean areCoPrime(int a, int b){ 
     int max = 0; 
     boolean flag = true; 
     if(a>=b) 
      max = a; 
     else 
      max = b; 
     for(int i=2;i<=max;i++) 
      if((a%i==0)&&(b%i==0)) 
       flag = false; 
     return flag; 
    } 
    public static void main(String[] args){ 
     Scanner scan = new Scanner(System.in); 
     int n = scan.nextInt(); 
     int sum = 0; 
     for(int k = 1;k<=n;k++){ 
      for(int p=2;p<=k;p++){ 
       for(int q=2;q<=k;q++){ 
        if(areCoPrime(p,q)&&(p*q==k)&&(p<=q)) 
         sum+=sum; 
       } 
      } 
     } 
     System.out.println(sum); 
    } 
} 

그래서 다른 1 < = K < = 12 따라서 함수 반환 0
들어 f(12) = 1
는 다른 최종 합계 1+1+1 = 3 (최종 출력) 여기서

결과 내 코드이다

이 코드를 실행할 때 출력은 3이되어야하지만 0이 나오고 솔루션을 찾을 수 없습니다.

Answer 1

당신은 (1), 우리는이 개 숫자가 서로 소 때를 알고 빠른 areCoPrime() 방법

를 들어 main()

에 중첩 루프의 수를 감소를 만들기

1. 하여 프로그램을 향상시킬 수 있습니다 그들의 최대 공약수 (GCD)는 1입니다. 유클리드 알고리즘이라고 불리는 GCD를 찾는 효율적인 방법입니다. (2), 당신은 두번째 루프 3 루프, p을 제거 할 수 있습니다 들어

   은 은 테스트 (아래에있는 내 수정 된 코드를 참조하십시오 sqrt(k)

   에 갈 필요가 : N = POW (10,6) 내 PC에서 2 초 미만 실행)

   import java.util.Scanner; 
   class ArthurFunction{ 
   
   public static boolean areCoPrime(int a, int b){ 
       if (GCD(a,b)==1) return true; 
       return false; 
   } 
   public static int GCD(int a, int b) { 
        if (b==0) return a; 
        return GCD(b,a%b); 
   } 
   
   public static void main(String[] args){ 
       Scanner scan = new Scanner(System.in); 
       int n = scan.nextInt(); 
       int sum = 0; 
       for(int k=1;k<=n;k++){   
        for(int p=2;p*p<k;p++){  
         if(k%p==0) {      
          int q = k/p;      
          if (areCoPrime(p,q)) sum++; 
         } 
        } 
       } 
       System.out.println(sum); 
   } 
   }