# 소수

7개의 포스트
post-thumbnail

[알고리즘]효율적인 소수 선별

본 글은 Bohyoh Shibata의 "자료구조와 함께 배우는 알고리즘 입문(자바편)"을 참고하여 작성하였습니다.특정 범위내의 소수를 선별하는 문제는 선별 대상 미만의 수로 해당 수를 나누는 방식으로 해결할 수 있다. 가령 100이하의 범위에서 소수를 선별하기 위해 2

2020년 3월 22일
·
0개의 댓글
post-thumbnail

[프로그래머스] 소수 찾기

파이썬으로 Level 2 소수 찾기 풀기!! 아우 어려워

2020년 2월 19일
·
2개의 댓글

수학1

나머지구하기컴퓨터는 처리할 수 있는 정수의 길이가 제한되어있다. 가끔씩 컴퓨터가 처리할 수 있는 범위를 벗어나는 아주 큰 수를 처리를 해야될 때가 있는데 이럴때 주로 답을 M으로 나눈 나머지를 구하라는 문제가 나온다. ( 정답을 M으로 나눈 나머지를 출력하라 )덧셈 :

2020년 2월 12일
·
0개의 댓글

소수를 구하는 알고리즘

소수 2를 제외한 자연수 중 나누어 떨어지는 수가 1과 자신뿐인 수 소수를 구하는 알고리즘 가장 기본적인 방법 정의를 그대로 구현한 것으로 2 부터 주어진 수 - 1 까지의 자연수로 계속 나누어 본다. O(n)의 시간복잡도를 가진다. 하지만, 숫자가 주어질 때 마다 판별해야한다. 메모이제이션 2 부터 n 사이의 소수로 나누었을 때 떨어지지 않으면 수수...

2020년 1월 26일
·
0개의 댓글

2019 winter PS --version Basic (day15)

백준 4849 -- 1) 백준 4849 : 베르트랑 공준 (https://www.acmicpc.net/problem/4948) n과 2n 사이의 소수 몇개인지 구하는 문제. 소수 구하는 거야 뭐 2에서 sqrt(n)까지 구하는 방법을 사용했고, 필요없는 계산의 반복을 막기위해 DP로 접근. 해당 수가 소수인지 아닌지를 알려주는 어레이 isPrime을 만...

2020년 1월 7일
·
0개의 댓글

백준 2960 에라토스테네스의 체 (Java)

풀이 소수를 저장 할 N+1개의 boolean배열을 만들어 2부터 N개까지 true로 세팅시켜준 후 이중 for문을 통해 2부터 차례대로 N까지의 배수자리의 배열을 false로 만들어주며 제거시켜주는데 이 때 제거 시 count를 세어 K값이 되었을 때 출력후 종료시킨다. (종료시키는 이유는 끝까지 돌면서 배열을 지울 시간을 쓸 필요가 없기 때문) 소스코...

2019년 12월 30일
·
0개의 댓글

programmer 소수 만들기

링크 두줄요약 n개의 수 중에서 3개를 선택할때 좋은 방법은 for문 중첩, 3개 까지는... 괜찮아 ㅎㅎ 숫자 k가 소수인지 판별할때는 logk(루트 k)까지만 검사해본다. 그 이상은 이미 검사된거니까!

2019년 1월 27일
·
0개의 댓글