λ³Έλ¬Έ λ°”λ‘œκ°€κΈ°
✨ Algorithm

[λ°±μ€€/C++] 11653번 : μ†ŒμΈμˆ˜λΆ„ν•΄

by nitronium102 2021. 8. 7.

문제

μ •μˆ˜ N이 μ£Όμ–΄μ‘Œμ„ λ•Œ, μ†ŒμΈμˆ˜λΆ„ν•΄ν•˜λŠ” ν”„λ‘œκ·Έλž¨μ„ μž‘μ„±ν•˜μ‹œμ˜€.

μž…λ ₯

첫째 쀄에 μ •μˆ˜ N (1 ≤ N ≤ 10,000,000)이 주어진닀.

좜λ ₯

N의 μ†ŒμΈμˆ˜λΆ„ν•΄ κ²°κ³Όλ₯Ό ν•œ 쀄에 ν•˜λ‚˜μ”© μ˜€λ¦„μ°¨μˆœμœΌλ‘œ 좜λ ₯ν•œλ‹€. N이 1인 경우 아무것도 좜λ ₯ν•˜μ§€ μ•ŠλŠ”λ‹€.

풀이

μ—λΌν† μŠ€ν…Œλ„€μŠ€μ˜ 체λ₯Ό ν™œμš©ν•˜λ©΄ κ°„λ‹¨νžˆ ν’€ 수 μžˆλŠ” λ¬Έμ œμ΄λ‹€. μ‚¬μš©ν•˜μ§€ μ•Šμ•„λ„ ν’€ μˆ˜λŠ” μžˆμ§€λ§Œ μ‹€ν–‰μ‹œκ°„μ΄ 크게 μ°¨μ΄λ‚œλ‹€.

(μœ„) 체 μ‚¬μš© / (μ•„λž˜) 체 μ‚¬μš©ν•˜μ§€ μ•ŠμŒ. (μ œν•œμ‹œκ°„ 1초)

 

μ†Œμˆ˜ νŒλ³„ μ•Œκ³ λ¦¬μ¦˜

01) κ°€μž₯ μ›μ΄ˆμ μΈ 방법

: 2λΆ€ν„° νŒλ³„ν•˜λŠ” 수 μ „κΉŒμ§€ λ‚˜λˆ λ³΄κ³  λ‚˜λ¨Έμ§€κ°€ 0이 μ•„λ‹ˆλ©΄ μ†Œμˆ˜λ‘œ μ •μ˜ν•˜λŠ” 방법. μΆ”μ²œν•˜μ§€ μ•ŠλŠ”λ‹€

02) λ°œμ „λœ 방법

: 2λΆ€ν„° ν•΄λ‹Ή 숫자의 root(N)κΉŒμ§€ ν™•μΈν•˜λŠ” 방법이닀. μ›λ¦¬λŠ” μ•½μˆ˜μ˜ 쀑심을 κ΅¬ν•˜λŠ” 과정이닀

- i <= sqrt(N)

- i*i <= N 이 두 λ°©μ‹μœΌλ‘œ ν‘œν˜„ν•œλ‹€

03) μ—λΌν† μŠ€ν…Œλ„€μŠ€μ˜ 체

μ†Œμˆ˜λ₯Ό νŒλ³„ν•  λ²”μœ„λ§ŒνΌ 배열을 ν• λ‹Ήν•˜μ—¬, ν•΄λ‹Ήν•˜λŠ” 값을 λ„£μ–΄μ£Όκ³  이후에 ν•˜λ‚˜μ”© μ§€μ›Œλ‚˜κ°€λŠ” 방법

01. 배열을 μƒμ„±ν•˜μ—¬ μ΄ˆκΈ°ν™”ν•œλ‹€.
02. 2λΆ€ν„° μ‹œμž‘ν•΄μ„œ νŠΉμ • 수의 λ°°μˆ˜μ— ν•΄λ‹Ήν•˜λŠ” 수λ₯Ό λͺ¨λ‘ μ§€μš΄λ‹€.(μ§€μšΈ λ•Œ μžκΈ°μžμ‹ μ€ μ§€μš°μ§€ μ•Šκ³ , 이미 μ§€μ›Œμ§„ μˆ˜λŠ” κ±΄λ„ˆλ›΄λ‹€.)
03. 2λΆ€ν„° μ‹œμž‘ν•˜μ—¬ λ‚¨μ•„μžˆλŠ” 수λ₯Ό λͺ¨λ‘ 좜λ ₯ν•œλ‹€.

이 λ¬Έμ œμ—μ„œλŠ” 2번째 풀이λ₯Ό μ‚¬μš©ν•˜μ˜€λ‹€.

#include <iostream>
#include <cmath>
using namespace std;

int main(){
    int N;
    cin >> N;
    if (N != 1){
    	// i*i <= N을 μ‚¬μš©ν•΄λ„ 무방
        for (int i=2; i<=sqrt(N); i++){
            while (N%i==0){
                cout << i << endl;
                N = N/i;
            }
        }
    }
    if (N > 1)
      cout << N << endl;
}

https://myjamong.tistory.com/139

 

μ†Œμˆ˜(Prime Number) κ΅¬ν•˜κΈ° 효율적 μ•Œκ³ λ¦¬μ¦˜ :: μ½”λ“œμžλͺ½

μ†Œμˆ˜(Prime Number) μ†Œμˆ˜λŠ” μžμ‹ λ³΄λ‹€ μž‘μ€ λ‘κ°œμ˜ μžμ—°μˆ˜λ₯Ό κ³±ν•˜μ—¬ λ§Œλ“€ 수 μ—†λŠ” 1보닀 큰 μžμ—°μˆ˜μ΄λ‹€. ex) 5λŠ” 5*1 λ˜λŠ” 1*5둜 수λ₯Ό κ³±ν•© κ²°κ³Όλ₯Ό μ λŠ” μœ μΌν•œ 방법이 κ·Έ 수 μžμ‹ μ„ ν¬ν•¨ν•˜κΈ° λ•Œλ¬Έμ— 5λŠ”

myjamong.tistory.com

 

λŒ“κΈ€