가장 빠른 알고리즘이 불분명 제목

Question

죄송 평방 응원 할 때 (근사하지)를,하지만 난 (편집 주시기 바랍니다) 제대로 명시하는 방법을 모른다, 그래서 예를 줄 것이다 :

을 SQRT (108) ~ 10.39 ...하지만 난이 SQRT처럼되고 싶어요 (108) = 6 *의 SQRT (3) 그래서 내 알고리즘

i = floor(sqrt(number))     //just in case, floor returns lowest integer value :) 
while (i > 0)       //in given example number 108 
    if (number mod (i*i) == 0) 
    first = i       //in given example first is 6 
    second = number/(i*i)    //in given example second is 3 
    i = 0 
    i-- 

에게 두 개의 숫자로

그래서 그건 확장을 의미합니다 어쩌면 당신은 더 나은 알고리즘을 알고 있습니까?

내가 PHP를 사용하고 물론 나는 적절한 구문

Answer 1

빠른 알고리즘이 없습니다. 모든 사각형 요소를 찾아야합니다. 이렇게하려면 적어도 일부 인수 분해가 필요합니다.

그러나 접근 방법의 속도를 상당히 높일 수 있습니다. 처음에는 n의 입방체 루트까지 소인수를 찾아서 Fastest way to determine if an integer's square root is an integer의 조언을 사용하여 n 자체가 완벽한 사각형인지 테스트해야합니다.

다음 속도가 올라감에 따라 아래에서 위로 작업합니다. 프라임 요소를 찾을 때마다 반복적으로 n을 나눠 사각형을 누적합니다. n의 크기를 줄이면 갈 수있는 한도를 줄이십시오. 이렇게하면 대부분의 숫자가 작은 숫자로 나눌 수 있다는 사실을 활용할 수 있으며, 고려해야 할 숫자의 크기가 빠르게 줄어들고 검색을 더 빨리 끝낼 수 있습니다.

다음 성능 향상은 어떤 번호에 대한 평가판을 더 스마트하게 만들기 시작합니다. 예를 들어 특별한 경우 2, 홀수만을 테스트하십시오. 알고리즘의 속도가 두 배가되었습니다.

그러나 이러한 모든 속도 향상에도 불구하고 방금보다 효율적인 무차별 대항력을 얻게됩니다. 그것은 여전히 ​​무력이며, 여전히 빠르지 않을 것입니다. (일반적으로 현재 아이디어보다 훨씬 더 빠르지 만)

여기에이 의사 코드가 있습니다.

integer_sqrt = 1 
remainder = 1 

# First we special case 2. 
while 0 == number % 4: 
    integer_sqrt *= 2 
    number /= 4 

if 0 == number/2: 
    number /= 2 
    remainder *= 2 

# Now we run through the odd numbers up to the cube root. 
# Note that beyond the cube root there is no way to factor this into 
# prime * prime * product_of_bigger_factors 
limit = floor(cube_root(number + 1)) 
i = 3 
while i <= limit: 
    if 0 == number % i: 
     while 0 == number % (i*i): 
      integer_sqrt *= i 
      number /= i*i 
     if 0 == number % (i*i): 
      number /= i 
      remainder *= i 
     limit = floor(cube_root(number + 1)) 
    i += 2 

# And finally check whether we landed on the square of a prime. 

possible_sqrt = floor(sqrt(number + 1)) 
if number == possible_sqrt * possible_sqrt: 
    integer_sqrt *= possible_sqrt 
else: 
    remainder *= number 

# And the answer is now integer_sqrt * sqrt(remainder) 

다양한 +1은 부동 소수점 숫자의 부정확성에 대한 문제를 피하기위한 것입니다. 여기에, 2700 알고리즘의 모든 단계를 통해 실행

이 일어나는 것이다 :

number = 2700 
integer_sqrt = 1 
remainder = 1 

enter while loop 
    number is divisible by 4 
     integer_sqrt *= 2 # now 2 
     number /= 4 # now 675 

    number is not divisible by 4 
     exit while loop 

number is not divisible by 2 

limit = floor(cube_root(number + 1)) # now 8 
i = 3 
enter while loop 
    i < =limit # 3 < 8 
     enter while loop 
      number is divisible by i*i # 9 divides 675 
       integer_sqrt *= 3 # now 6 
       number /= 9 # now 75 

      number is not divisible by i*i # 9 does not divide 75 
       exit while loop 

     i divides number # 3 divides 75 
      number /= 3 # now 25 
      remainder *= 3 # now 3 

     limit = floor(cube_root(number + 1)) # now 2 

    i += 2 # now 5 

    i is not <= limit # 5 > 2 
     exit while loop 

possible_sqrt = floor(sqrt(number + 1)) # 5 

number == possible_sqrt * possible_sqrt # 25 = 5 * 5 
    integer_sqrt *= possible_sqrt # now 30 

# and now answer is integer_sqrt * sqrt(remainder) ie 30 * sqrt(3) 

Answer 2

그것은 이것에 대한 빠른 알고리즘이 있다는 확률이 낮다을 사용합니다 중요합니다. 예를 들어, 증가하는 순서로 모든 주요 제수 https://mathoverflow.net/questions/16098/complexity-of-testing-integer-square-freeness 특히 https://mathoverflow.net/questions/16098/complexity-of-testing-integer-square-freeness/16100#16100

Answer 3

1. 목록을 참조하십시오 2700 = 2 * 2 * 3 * 3 * 3 * 5 * 5. 이것은 가장 느린 단계이며 sqrt (N) 작업이 필요합니다.
2. 누적 계산기를 만듭니다 (1로 시작). 이 목록을 스캔하십시오. 모든 쌍의 수에 대해 누산기를 그 중 하나 (하나)로 곱하십시오. 위의 목록을 스캔 한 후 2 * 3 * 5가됩니다.
3. 누산기가 승수입니다. 나머지는 제곱근 아래에 있습니다.