소인수분해
수학...소인수분해랑 소수가 뭔지는 확실히 알았다
🎠 기억하고 싶은 부분🎠
1. 소수 찾기
수학이란 신기해
a * b = n 으로 n의 모든 약수를 구하면 a 또는 b 둘 중에 하나는 무조건 √N 이하래!
그니까 1을 제외하고√N 이하의 값으로 N이 나눠지면 소수가 아닌거지!
2. list -> int 배열 변환
array=list.stream().mapToInt(i->i).toArray();
3. Math.sqrt(자연수)
자연수 루트 씌우기
소수 -> 1과 자기자신으로만 나눠지는 수
소인수분해 -> 특정수를 소수들의 곱으로만 표현하는 것
🎯 문제
소인수분해란 어떤 수를 소수들의 곱으로 표현하는 것입니다. 예를 들어 12를 소인수 분해하면 2 2 3 으로 나타낼 수 있습니다. 따라서 12의 소인수는 2와 3입니다. 자연수 n이 매개변수로 주어질 때 n의 소인수를 오름차순으로 담은 배열을 return하도록 solution 함수를 완성해주세요.
<제한사항>
2 ≤ n ≤ 10,000| n | result |
|---|---|
| 12 | [2, 3] |
| 17 | [17] |
| 420 | [2, 3, 5, 7] |
⛳ 답안
import java.util.ArrayList;
import java.util.List;
class Solution {
public int[] solution(int n) {
List<Integer> list=new ArrayList<>();
int[] answer= new int[list.size()];
for(int i=2; i<=n; i++) {
// n을 나눌 수 있는 값부터 찾고
if(n%i==0) {
int temp=0;
// 그 값이 소수인지 찾기
for(int j=2; j<=Math.sqrt(i); j++) {
// 소수가 아니면 break;
if(i%j==0) {temp=-1; break;}
else temp=1;
}
// 결과가 소수였으면 list에 넣어주기
if(temp==1 || i==2 || i==3) {list.add(i);}
}
}
answer=list.stream().mapToInt(i->i).toArray();
return answer;
}
}🎲 과정
내가 컴퓨터로 소인수분해를 해보는 날이 오다니...
일단 소인수분해라는 단어가 나온 순간부터 막막해서 n이하로 반복문 돌려서 나눠떨어지면서 i가 소수인 수를 구하는 방법밖에 생각이 안났다.
그래서 약간 저게 맞나...?싶은 결과물이 나와버렸어
암튼 n을 나눌 수 있는 i값을 찾고 그 i값에 대해 for문을 한번 더 돌려서 소수찾았다.
이때 i가 소수인지 찾는게 좀 어려워서 인터넷을 뒤졌다...!
소수인 값을 찾으려면 일단 0과 1은 제외시키고 √N 이하의 값으로 나눴을때 나눠지는 값을 제외시키면 된대
예를 들어 자연수가 16일 때 a * b 로 두수의 곱을 표현하면
1 × 16
2 × 8
4 × 4
8 × 2
16 × 1
a와 b중 하나는 무조건 √N 보다 작거나 같대
수학은 신기해 싱기방기야
암튼 그래서 저거 Math.sqrt(n)로 조건 줘가지고 풀었다.
근데 1은 모든 수가 다 나눠지니까 조건을 2부터 줬더니 2랑 3은 저 조건문을 통과를 못해가지고 그냥 2,3이면 억지로 list에 값 넣어줘버렸다.
2랑 3까지 넣으려면 조건 어떻게 해야되는걸까...어렵다 어려워
