일부 정수 n의 요인으로 가장 큰 요인 수를 찾는 알고리즘을 설계하고 있습니다. 이 문제는 R.G.Dormey가 "컴퓨터로 해결하는 방법"에 나와 있습니다. 그 정수가 아닌일부 계급에서 가장 큰 요인 수 n이
먼저 확인 : 당신이 알고리즘을 설계에 대해 이동하는 방법에 나를 도울 수 .. 답은 정수 n의 요소와도 계승 수 .. 내가 생각
솔루션이어야한다 초기. 프라임 경우가 계승 숫자인지 아닌지, 더 이상의 솔루션 추적 할 수없는 가망 ..
주요 아니라면, 즉이있다,
예 경우 .. 정수
검사의 가장 큰 요인을 찾을 수 없습니다 ..
그것이 계승 번호 또는하지 경우확인 ...
을
없는 경우 답변 정수의 두 번째로 큰 요소를 찾아 nd so on ...
정수로가는 가장 큰 계승을 찾으려면 꾸준히 요인을 늘려야합니다. 나는. 결과 정수가 2, 3, 4 등으로 나눌 수 있는지 확인하십시오. 처음 오류가 발생하면 더 큰 계승으로 정수를 나눌 수 없습니다. 예 : 정수가 2 ... 6로 나눌 수 있지만 7이 아니라면 6이라는 답을 알 수 있습니다.
-1 : 정수가 2 ... 5가 아닌 6으로 나눌 수있는 경우, 이상한 숫자가 있습니다. 그것은 2와 3으로 나눌 수 있지만 6으로 나눌 수 없습니다. 허용 된 대답 인 것처럼 보이지만 이것은 잘못된 것입니다! –
그 예일뿐입니다. 방법은 절대적으로 옳다. 그것은 효과가 있었다. 이 답변은 아래의 Dennis의 대답과 같습니다. – KawaiKx
숫자 60은 2, 3, 4, 5 및 6으로 나눌 수 있지만 7로 나눌 수는 없습니다. 그러나 6! 대답이 아닙니다. –
N을 1로 나눈 다음 결과를 2로 나눈 다음 결과를 3, ... 그리고 k + 1로 나눕니다. k + 1에 대한 정수 결과가 없으면 k! 대답입니다.
+1 :이 답변은 정확합니다. 비록 내가 k라고 말할 것입니다! ** ** 대답입니다. –
factorials의 속성이 매우 매우 빠르게 커지면 ... 직접 나누려는 유혹을받을 것입니다. 먼저 숫자보다 작은 계승을 찾으십시오. 을 다음과 같이 나눕니다. factorial f (fac, num)를 귀하의 수보다 적은 계승을 반환하는 계승 함수로합시다. 그런 num! = fac 다음을 수행하십시오.
(N % fac) == 0을 확인하십시오. (N * num) % fac 다음에 (N * num) * (num-1) % fac
답변은 다음과 같은 경우에 첫 번째 경우 (num-1) 여기
long prod = 1;
long maxFactor = 1;
for(long i=2; i<=n && prod< n && n%i==0 ;i++){
prod = prod*i;
if(n%prod == 0) maxFactor = prod;
}
n에 그의 가장 큰 요인 요인 우리가 찾아야하고 macFactor의 최종 값은 최종 솔루션입니다 수입니다.
참고 : 숫자 요소의 요인도 숫자의 요소입니다.
인자가 계승 값은 다음이다은 1에서 시작하여 연속적인 정수 제품
#include<stdio.h>
main()
{
int i,n;
scanf("%d",&n);
for(i=2;n>1&&n%i==0;i++)
n/=i;
printf("%d",i-1);
}
N이 입력된다 (즉 그 자체 이외의 계수의 곱해야 함)해야한다면 숫자
테스트 할 최대 정수는 무엇입니까? –
좋은 지적 .. 나는 그 생각을하지 않았다. 나는 짧은 숫자를 숫자로 생각했다.그래서 그것은 65535 – KawaiKx
이 될 것입니다. 당신은 factorials의 테이블을'8까지만 필요로합니다! == 40320' 그리고 나서 이들 중 어느 것이 당신의 목표 숫자로 정확히 나뉘어 지는지 테스트 할 수 있습니다. 32 비트 부호없는 int를 사용하더라도'12! '까지만 올면됩니다. –