최대 질량 인 수 를 구하 다.

목차

내 가 좋아 하 는 프로 그래 밍 제목 을 적어 라

지식 도입

전통 적 으로 최대 질량 인 수 를 구 하 는 방법

총화

제 가 좋아 하 는 프로 그래 밍 문 제 를 적어 주세요.
시간 제한: C / C + + 1 초, 기타 언어 2 초 공간 제한: C / C + 32M, 기타 언어 64M 열도 지수: 5819 본 문제 지식 점: 문자열 수학 문제 설명 은 주어진 문자 서열 에 대해 왼쪽 에서 오른쪽으로 모든 숫자 문 자 를 꺼 내 기호 없 는 정수 로 연결 합 니 다 (문자 배열 의 길 이 는 100 보다 적 고 맞 춤 형 정 수 는 2 ^ 31 보다 작 습 니 다).이 정수 의 최대 소수 인자 (소수 라면 최대 인 자 는 자신) 를 계산 하고 출력 합 니 다. 입력 설명: 여러 개의 데이터 가 있 고 데 이 터 를 입력 하 는 첫 번 째 행 위 는 정수 이 며 문자 시퀀스 의 수 를 나타 내 며 각 조 의 데 이 터 는 한 줄 의 문자 시퀀스 입 니 다.출력 설명: 모든 문자 시퀀스 에 대해 소득 정수 의 최대 요소 인 자 를 추출 합 니 다. 만약 에 문자 시퀀스 에 숫자 가 없 거나 찾 은 정수 가 0 이면 출력 0 이 고 모든 정수 가 한 줄 의 출력 을 차지 합 니 다.
예시 1 입력 3 sdf0ejg 3. f?9f ?4afd0s&2d79*(g abcde
출력
지식 도입
우선 한 수의 질량 인수 에 대해 너 는 이것들 을 알 아야 한다.

모든 수 는 반드시 많은 소수 (질 수) 의 곱

로 나 타 낼 수 있다.

소수 x 소수 = 합 수, 소수 x 합 수 = 합 수, 합 수 x 합 수 = 합 수

만약 에 하나의 합 수 n 이 √ n 을 초과 하 는 질 적 인수 가 있다 면 있 고 하나 밖 에 없 으 며 자신

이다.
이곳 을 보면 너 는 여전히 비교적 빙빙 돌 고 있 을 것 이다. 괜찮아, 조금 있 으 면 이 몇 가지 성질 이 하나하나 위력 을 나 타 낼 것 이다.
전통 적 으로 최대 질량 인 수 를 구 하 는 방법

가장 번 거 로 운 것 은 하나씩 옮 겨 다 니 는 것 이다. 먼저 질 수 를 판단 하 는 함 수 를 쓴 다음 에 for (int i = n; i > 2; – i) 는 조건 을 만족 시 키 면 i 가 n 으로 정리 되 고 i 가 소수 라면 break 로 최대 의 질 인 수 를 얻 을 수 있다. 매우 느 리 고 직접 시간 초과

조금 높 아진 알고리즘

int GetMaxPrime(int n) {
	int i = 2;
	int res = 1;
	while (n > 2) {
		if (n%i == 0) {
			n /= i;
			res = i;
		}	
		else
			i++;
	}
	return res;
}

코드 의 원 리 는 어 렸 을 때 부터 크게 다가 가 는 것 입 니 다. 저 는 당신 이 n 이 아무리 크 더 라 도 저 는 가능 한 한 작은 숫자 를 사용 하 겠 습 니 다. 여 기 는 i 가 당신 을 조금씩 착취 하 는 것 입 니 다. 이렇게 하 는 목적 은 원래 당신 이 저 보다 i 가 큰 합 수 는 모두 i 에 의 해 분할 되 었 습 니 다. 그 결과 제 while 를 거 친 후에 i 를 정리 할 수 있 는 합 수 는 모두 i x i x... x 합 수 가 되 었 습 니 다.또는 소수, 즉, 아래 의 모양 이 되 었 습 니 다: n = i x i x i x... x 합 수 또는 소수 x 합 수 또는 소수 운 이 하마터면 소수 가 될 뻔 했 습 니 다. 운 이 좋 은 것 은 다른 인수 가 있 기 때문에 합 수 를 했 습 니 다. 그래서 살아 남 았 습 니 다. 이런 것 은 무엇 을 의미 합 니까? 사실 그들 은 소수 가 반드시 i 보다 클 것 이라는 특징 이 있 습 니 다. 그렇지 않 으 면 i 이전의 숫자 에 의 해 이미 분할 되 었 습 니 다.; 합 수의 인 수 는 반드시 i 보다 클 것 이다 (1 제외)즉, 뒤에 있 는 것 이 합 수 든 소수 든 소 수 는 변 하지 않 을 수 있 습 니 다. i 의 크기 = 이 소 수 를 제외 하고 이 소 수 는 1 로 변 합 니 다. 합 수 를 하면 i 보다 작은 인수 가 없 을 것 입 니 다. 그렇지 않 으 면 i 이전의 숫자 에 의 해 착취 되 었 기 때문에 뒤의 i 에 의 해 소수 로 나 눌 수 있 습 니 다. 이런 소 수 는 i 보다 크 고 i 가 느 리 기 를 기다 리 고 있 습 니 다.천천히 커 져 서 그들 을 1 로 나 누 었 습 니 다. i 는 이때 오른쪽 에 남 은 소수 와 같 을 때 까지 n 은 1 로 끝 납 니 다. 우 리 는 가장 큰 소 수 는 i 가 이 숫자 와 같 을 때 까지 식 오른쪽 에 숨 어 있 었 다 는 것 을 알 수 있 습 니 다.

더 빠 른 방법

int max_yinzi(int n)
{
    int max =0;
    for(int i=2;i<=int(sqrt(n));i++)// 2   n     
    {
        while(n%i==0)              //             ，     while，   if
        {
            max = i;               // max       
            n /= i;                //     
        }
        if(n==1)
            break;
    }
    if(n!=1)                       //  n   1，          n    ，      ，      n
        max = n;
    return max;
}

세 번 째 방법 은 두 번 째 방법 과 비슷 한 점 이 있 지만 관건 적 인 부분 에서 향상 되 었 습 니 다. 우 리 는 두 번 째 방법 이 종료 되 는 조건 은 n = 1 이라는 것 을 알 게 되 었 습 니 다. 즉, 이때 i 는 가장 큰 소수 = 이때 의 n 과 같 습 니 다. 그리고 나 누 면 1 이 되 고 이때 멈 추 면 됩 니 다. 세 번 째 방법 은 다 그렇지 않 습 니 다. 관건 은 어디 에 있 습 니까?? 이때 주의 성 3:
만약 에 하나의 합 수 n 이 √ n 을 초과 하 는 질 적 인수 가 있다 면 있 고 하나 밖 에 없 으 며 자신 을 위해
즉, 이 합 수의 최대 질량 인 수 는 두 가지 상황 이 있다.

자체

√ n

보다 작 음
분명 한 방법 2 는 이것 을 구분 하지 않 고 계속 운행 한다. 사실은 i 가 √ n 을 초과 한 후에 모두 열심히 공부 하지 않 고 while 를 집행 하지 않 고 i + + 를 계속 할 것 이다. i = 이때 의 n 까지 사실은 √ n 일 때 n 이 라 고 판단 할 수 있 기 때문에 여 기 는 가지치기 작업 에 해당 한다.
코드 에 세부 사항 이 있 습 니 다. 바로 for 순환 의 종료 조건 i < = int (sqrt (n)) 에서 n 은 변화 하 는 것 입 니 다. 이것 은 위 에서 말 한 한 마디 와 관계 가 있 습 니 다. 즉,
가장 큰 소 수 는 식 오른쪽 에 숨겨 져 있 습 니 다. 생동감 있 게 말 하면 n = i x i x... i x (n / i) (n / i > i)
이때 n 의 최대 질량 인 수 를 구 하 는 것 과 n / i 의 최대 질량 인 수 는 같다. (n / i)소수 든 합 수 든 소수 든 절약 할 수 있 고 합 수 든 더 많은 착취 가 필요 하 다. 두 가 지 를 구 하 는 것 이 같은 효 과 를 가 진 이상 for 순환 의 조건 은 당연히 더욱 편리 한 방향 으로 바 뀌 어야 한다. 즉, n 과 n / i 가 더 작은 것 을 취하 면 당연히 n / i 가 되 어야 한다. 그러면 누군가가 n / i 를 구 하 는 가장 큰 요인 이 라면 이때 i 를 구 해 야 하 는 것 이 아니 냐 고 물 을 수 있다.n / i 에 게 i1
총결산
제 설명 은 쉽게 알 아 듣 지 못 할 수도 있 습 니 다. 제 문자 표 현 력 에 한계 가 있 습 니 다. 여러분 은 코드 에 따라 스스로 깨 닫 고 양 해 를 구 할 수 있 습 니 다.