# 1929

dangdang

https://www.acmicpc.net/problem/1929 📔문제 M이상 N이하의 소수를 모두 출력하는 프로그램을 작성하시오. 📝입력 첫째 줄에 자연수 M과 N이 빈 칸을 사이에 두고 주어진다. (1 ≤ M ≤ N ≤ 1,000,000) M이상 N이하의 소수가 하나 이상 있는 입력만 주어진다. 📺출력 한 줄에 하나씩, 증가하는 순서대로 소수를 출력한다. 📝예제 입력 1 📺예제 출력 1 🔍출처 -데이터를 추가한 사람: jinjean0123, yongjun042 🧮알고리즘 분류 수학 정수론 소수 판정 에라토스테네스의 체 📃소스 코드 📰출력 결과 ![](https://velog.velcdn.com/images/dangdang/post/da3e83e8-b5ba-4418-be17-cad047f

kyunghun96

이전에 풀었던 문제와 사실 동일하다. 특정 수의 제곱근 만큼만 반복문을 돌려 소수를 판별하는 문제다. 특정 수의 제곱근만 반복분을 돌리는 이유는 아래와 같은 이유로 알 수 있다. 백준 1929

montag

1929번 소수 구하기 > ### 문제 M이상 N이하의 소수를 모두 출력하는 프로그램을 작성하시오. > ### 입력 첫째 줄에 자연수 M과 N이 빈 칸을 사이에 두고 주어진다. (1 ≤ M ≤ N ≤ 1,000,000) M이상 N이하의 소수가 하나 이상 있는 입력만 주어진다. > ### 출력 한 줄에 하나씩, 증가하는 순서대로 소수를 출력한다. > ### 예제 입력 1 3 16 > ### 예제 출력 1 3 5 7 11 13 나의 풀이 전에 풀었던 문제처럼 반복문을 통해 1부터 해당 숫자까지 나눠보고 cnt를 통해 나눠진 횟수를 +시켜줬다 그리고 cnt가 1인 것만 출력하는 코드를 작성했다 결과는 시간초과... 아마도 숫자 하나가 소수인지 구하는 데 2~i 연산을

sodamjeong

1929번 소수 구하기 입력하는 두 수를 포함하여 두 수 사이의 소수를 오름차순으로 출력하는 문제. 숫자 범위가 커서 시간 초과를 걱정 했는데 역시나 연속 시간초과가 되었던 문제였다.. 이중 for 문에 리스트의 조합으로 시간 초과가 되어버렸다. 어떻게든 for 문을 줄여보려고 계속 붙잡고 있었지만 도저히 판단이 안서서 검색해볼 수 밖에 없었다ㅠ 결국 검색해서 통과했다. 이런 방법도 있다는걸 까먹지 않기 위해 다시 쳐보기도 하고 또 다른 방법도 있는지 검색해 봤다. 이런 방법도 있다니 ..! 작은 소수를 출력하고 그 소수의 배수들은 모두 0으로 바꿔 출력하지 않도록 했다. 1개의 for문과 1개의 list로 깔끔하게 정리할 수 있어 좋은 코드인 것 같다. 다양한 방법이 있다는 걸 잊지

ro_sie

📚 문제 정의 M이상 N이하의 소수를 모두 출력하는 프로그램을 작성하시오. 📝 입력 첫째 줄에 자연수 M과 N이 빈 칸을 사이에 두고 주어진다. (1 ≤ M ≤ N ≤ 1,000,000) M이상 N이하의 소수가 하나 이상 있는 입력만 주어진다. 예제 입력 1 📝 출력 한 줄에 하나씩, 증가하는 순서대로 소수를 출력한다. 예제 출력 1 💡 코드

tting

내가 생각한 구조는 M~N을 돌면서 소수 검사를 하고 만약 나누어 떨어지면(소수가 아니면) 플래그 변수 1로 바꾸고 바로 빠져나옴 --> flag변수 0일때만 출력시킴 이다 이렇게 적었더니 시간 초과가 떴다 찾아보니 n-1까지 반복문을 돌릴게 아니라 루트n까지만 돌리는거였다 게다가 (M, N+1)인데 범위도 틀렸다 ㄴ아직 파이썬이 익숙치 않다-끝문자 포함 안되는 것임! 암튼 루트n으로 고치는데 float라 안되고 올림을 시켜주면 3이 문제다 for문이 2부터 시작인데 루트3을 올림하면 2이다 결국 range(2,2)가 되어 동작하지 않는다.. +제출시에는 출력초과가 뜬다 https://leejunggae.tistory.com/3 를 참고해 소수 아닌 수의 배수를 없애는 아이디어로 작성했으나 3중 반복문이 되어 시간초과 ^이렇게 수정하여 성공 루트 변환 함수 math.sqrt() 소수 변환 함수 올림 math.ceil(n) 내림 math.flo

1-blue

백준 알고리즘 기초 강의에 명시된 문제를 풀이한 포스트입니다 1. 10430번 - 나머지 2. 2609번 - 최대공약수와 최소공배수 3. 1978번 - 소수 찾기 4. 1929번 - 소수 구하기 5. 6588번 - 골드바흐의 추측 6. 10872번 - 팩토리얼 7. [1676번 - 팩토리얼 0의 개수](https://www.acmicpc.n

qlwb7187

출처 | https://www.acmicpc.net/problem/1929 문제 M이상 N이하의 소수를 모두 출력하는 프로그램을 작성하시오. 입력 첫째 줄에 자연수 M과 N이 빈 칸을 사이에 두고 주어진다. (1 ≤ M ≤ N ≤ 1,000,000) M이상 N이하의 소수가 하나 이상 있는 입력만 주어진다. 출력 한 줄에 하나씩, 증가하는 순서대로 소수를 출력한다. 코드 느낀점 : cost가 많이 발생한다. 다른 방법을 모색해보자.

qlwb7187

출처 | https://www.acmicpc.net/problem/11653 문제 정수 N이 주어졌을 때, 소인수분해하는 프로그램을 작성하시오. 출력 N의 소인수분해 결과를 한 줄에 하나씩 오름차순으로 출력한다. N이 1인 경우 아무것도 출력하지 않는다. 입력 첫째 줄에 정수 N (1 ≤ N ≤ 10,000,000)이 주어진다. 코드

5p2rs5

코드 보시기 전에 시간초과는 입출력을 C언어 방식으로 해보세요. 에라토스테네스의 체를 가지고 푸는 문제입니다. 0과 1을 제외한 2부터 시작하여 배열안에 2의 배수들을 전부 지우고 그 다음 3, 그 다음은 4.... 이렇게 지원나가면 소수들의 배수가 전부 지워지기 때문에 소수만 들어있는 배열만 구할 수 있습니다.

blooper20

문제 M이상 N이하의 소수를 모두 출력하는 프로그램을 작성하시오. 입력 출력 예제 입력 1 예제 출력 1 첫번째 시도 정답 이 문제를 풀때 항상 시간초과로 틀리는데 시간을 줄이는 방법을 잘 모르겠다.

y7y1h13

에라토스테네스 체를 사용해서 풀었다. 약수를 이용하면 시간을 많이 줄일 수 있다.

donggle_22

[BOJ] 3052번 나머지 https://www.acmicpc.net/problem/3052 중복되는 걸 빼고 집합을 출력하려면 set() 함수를 써준다! 내가 짠 코드 : [BOJ] 1929번 소수 구하기 https://www.acmicpc.net/problem/1929 자꾸 시간초과가 나서 검색해봤더니 내가 짠 코드 : 소수인지 검사할때 2부터 i까지 검사하는 것이 아니라 2부터 i의 제곱근까지만 검사하면 나머지는 검사하나 마나라고 했다! 제곱근 구하면 float 형으로 자질자질 되므로 int형으로 변경 1은 소수가 아니므로 제외해줌 -> 얘 때매 애먹음..;; 수정 후 코드 : ✔ 한 일 점검 백준 - 1문제 이상⭕ 스프링 - 섹션1, 2🔺 파이썬 - 이코테로 문법 정리❌ ✔ 내일 목표 백준 - 1문제 이상 스프링 - 섹션1, 2 파이썬 - 이코테로

younoah

1929번 소수 구하기 문제 M이상 N이하의 소수를 모두 출력하는 프로그램을 작성하시오. 입력 첫째 줄에 자연수 M과 N이 빈 칸을 사이에 두고 주어진다. (1 ≤ M ≤ N ≤ 1,000,000) M이상 N이하의 소수가 하나 이상 있는 입력만 주어진다. 출력 한 줄에 하나씩, 증가하는 순서대로 소수를 출력한다. 예제 입력 1 복사 예제 출력 1 복사 코드 풀이 소수 : 1과 자기 자신만을 약수로 갖는 수 반복문 범위 n의 약수는 n의 절반을 넘길수 없다. i <= n / 2 i * i <= n , i <= Math.sqrt(n)

jini_eun

Baekjoon Online Judge algorithm practice 단계별 문제풀기 9. 기본 수학2 Java / Python 4. 소수 구하기 1929번 > 에라토스테네스의 체로 풀어 봅시다. >> 에라토스테네스의 체란 간단하게 말해서, 일정 범위내 수열에서 배수들을 제거해 소수만 남기는 방법이다. 예를 들어) 수열 [2 3 4 5 6 7 8 9 10] 에서 2의 배수 제거 => [2 3 5 7 9] 에서 3의 배수 제거 => [2 3 5 7] 와 같은 방식이다. 즉, 말그대로 체로 걸러서 소수만 남기는 원리이다. Java Python > 오늘은 기본 수학2 예제였습니다! 소수를 구하기 위해 에라토스테네스의 체에 대해 공부하고, 구현 방법에 대해 검색해보고 참고하며 구현할 수