1^14 의 square root 는 1^7이다.

1^7까지의 소수만 구해주면 된다.


그래서 2~1^7까지의 소수를 구하고, 

#include <cstdio>
/**
* https://www.acmicpc.net/problem/1456
* BOJ 백준온라인져지 1456 거의 소수 풀이
*/
int main(){
long long min, max;
int count = 0;
scanf("%lld%lld", &min, &max);
bool *isPrimeNumber = new bool[(int)1e+7 + 1];
int *primeNumber = new int[(int)1e+7 + 1];
int cnt = 0;
for(long long i = 2; i * i <= max ; i++){
if(!isPrimeNumber[i]){
for(long long j = i * 2; j * j <= max; j += i) isPrimeNumber[j] = true;
primeNumber[cnt++] = i;
}
}
for(int i = 0; i < cnt; i++){
long long n = primeNumber[i];
while(primeNumber[i] <= max / n){
if(primeNumber[i] * n >= min) count++;
n *= primeNumber[i];
}
}
printf("%d", count);
}
view raw BOJ_1456.cpp hosted with ❤ by GitHub


primeNumber에 소수들을 넣어준다.


primeNumber에 들어간 소수들로 

max => n * primeNumber[i]를 계산해준다.


여기서 주의해야 될 점이 n이 long long을 넘어가는 경우다.


하지만 이항을 해서

max / n >= primeNumber[i]로 변경할 수 있다.


그리고 min >=의 경우를 구해야줘야 되는데, 이미 while loop에서 체크를 해줘서 밑에서는 체크를 안해줘도 된다.

저작자표시

'IT > 알고리즘' 카테고리의 다른 글

BOJ 백준온라인져지 2206 벽 부수고 이동하기 풀이  (0) 2017.12.15
BOJ 백준온라인져지 14923 미로탈출 풀이  (0) 2017.12.15
BOJ 백준온라인져지 14921 용액 합성하기 풀이  (0) 2017.12.14
BOJ 백준온라인져지 2530 인공지능 시계 풀이  (0) 2017.12.14
BOJ 백준온라인져지 2525 오븐 시계 풀이  (0) 2017.12.14

에라토스테네스의 체를 이용해서 소수들을 구하고


시간복잡도를 줄여주기 위해


i -= 2 를 해줬다.


그리고 for loop을 2개 중첩안시킴

#include <cstdio>
#include <math.h>
/**
* https://www.acmicpc.net/problem/6588
* BOJ 백준온라인져지 6588 골드바흐의 추측 풀이
*/
#define MAX 1000001
int main(){
int *isPrimeNumber = new int[MAX];
for(int i = 2; i < MAX ; i++) isPrimeNumber[i] = true;
for(int i = 2, squareRoot = sqrt(MAX); i <= squareRoot; i++){
if(isPrimeNumber[i])
for(int j = i * i; j < MAX ; j += i)
isPrimeNumber[j] = false;
}
while(1){
int N;
scanf("%d", &N);
if(N){
int loopStartNumber = N - 1;
bool isPrint = false;
for(int i = loopStartNumber, NDivided = N / 2; i >= NDivided && !isPrint; i -= 2){
if(isPrimeNumber[i] && isPrimeNumber[N - i]){
printf("%d = %d + %d", N, N - i, i);
isPrint = true;
}
}
if(!isPrint) printf("Goldbach's conjecture is wrong.");
printf("\n");
}else break;
}
}
view raw BOJ_6588.cpp hosted with ❤ by GitHub
저작자표시

'IT > 알고리즘' 카테고리의 다른 글

BOJ 백준온라인져지 11047 동전 0 풀이  (0) 2017.12.07
BOJ 백준온라인져지 1016 제곱 ㄴㄴ 수 풀이  (0) 2017.12.06
BOJ 백준온라인져지 2960 에라토스테네스의 체 풀이  (0) 2017.12.06
BOJ 백준온라인져지 2490 윷놀이 풀이  (0) 2017.12.05
BOJ 백준온라인져지 10872 팩토리얼 풀이  (0) 2017.12.05

에라토스테네스의 체의 방법을 사용하는데, 소수를 구하는게 목적이 아니고 K 번째 지워지는 숫자를 구하는게 목적

#include <cstdio>
/**
* https://www.acmicpc.net/problem/2960
* BOJ 백준온라인져지 2960 에라토스테네스의 체 풀이
*/
int main(){
int N,K;
scanf("%d%d",&N,&K);
bool *isPrimeNumber = new bool[N+1];
int count = 0, result = 0;
for(int i = 2; i <= N; i++){
if(!isPrimeNumber[i]){
for(int j = i; j <= N; j += i){
if(!isPrimeNumber[j]){
isPrimeNumber[j] = true, count++;
if(count == K) result = j;
}
}
}
}
printf("%d", result);
}
view raw BOJ_2960.cpp hosted with ❤ by GitHub


저작자표시

'IT > 알고리즘' 카테고리의 다른 글

BOJ 백준온라인져지 1016 제곱 ㄴㄴ 수 풀이  (0) 2017.12.06
BOJ 백준온라인져지 6588 골드바흐의 추측 풀이  (0) 2017.12.06
BOJ 백준온라인져지 2490 윷놀이 풀이  (0) 2017.12.05
BOJ 백준온라인져지 10872 팩토리얼 풀이  (0) 2017.12.05
BOJ 백준온라인져지 1037 약수 풀이  (0) 2017.12.05

아이디어 :

1. 에라토스테네스의 체를 이용해서 소수를 구한다.

2. 소수를 primeNumber에 하나씩 넣어준다. 마지막값은 0이다.

3. 2... 돌게되면 0이 나오는데 0이면 반복문을 종료한다.

4. 반복문 안에 반복문을 넣어서 값을 더해주고 맞으면 빼기한 값을 저장하고 그걸로 체크를한다.



더 좋은 방법.


어차피 빼기값을 최소로 구하는거니까. n/2부터 시작해서 하나씩 빼면서 맞는답이 나오면 바로 출력하면 더 빠르다.

이 방법을 사용하면 2번 과정이 없어진다.


더 좋은 방법을 사용한다면,

O(Nnlgn)이 될거같다.

#include <cstdio>
/**
* https://www.acmicpc.net/problem/9020
* BOJ 백준온라인져지 9020 골드바흐의 추측 풀이
*/
#define MAX 10001
int main(){
bool isPrime[MAX-1] = {};
for(int i=2; i<MAX; i++) isPrime[i]=true;
for(int i=2; (i*i)<MAX; i++){
if(isPrime[i]){
for(int j=i*i; j<MAX; j+=i) isPrime[j]=false;
}
}
int idx = 0;
int primeNumber[MAX-1] = {};
for(int i = 2; i<MAX; i++) if(isPrime[i]) primeNumber[idx++] = i;
int N;
scanf("%d",&N);
while(N--){
int n;
scanf("%d",&n);
int min = MAX, tempI = 0, tempJ = 0, result = 0;
for(int i = 0; i < idx && result < n; i++){
result = primeNumber[i];
for(int j = i; j < idx && result + primeNumber[j] <= n; j++){
if(result + primeNumber[j] == n){
int subtraction = primeNumber[j] - result;
if(min > subtraction){
min = subtraction;
tempI = i;
tempJ = j;
}
}
}
}
printf("%d %d\n",primeNumber[tempI],primeNumber[tempJ]);
}
return 0;
}
view raw BOJ_9020.cpp hosted with ❤ by GitHub


저작자표시

'IT > 알고리즘' 카테고리의 다른 글

BOJ 백준온라인져지 2504 괄호의 값 풀이  (0) 2017.11.28
BOJ 백준온라인져지 1874 스택 수열 풀이  (0) 2017.11.27
BOJ 백준온라인져지 4948 베르트랑 공준 풀이  (0) 2017.11.24
BOJ 백준온라인져지 1181 단어 정렬 풀이  (0) 2017.11.23
BOJ 백준온라인져지 1427 소트인사이드 풀이  (0) 2017.11.22

문제를 딱 보고.

아 이건! 미리 구해놓고 하나씩 출력하면 될듯~


에라토스테네스의 체를 복습했다.


#include <cstdio>
/**
* https://www.acmicpc.net/problem/4948
* BOJ 백준온라인져지 4948 베르트랑 공준 풀이
*/
int main(){
int N = 1;
bool isPrime[123456*2+1] = {};
for(int i=2; i<=123456*2; i++) isPrime[i]=true;
for(int i=2; (i*i)<=123456*2; i++){
if(isPrime[i]){
for(int j=i*i; j<=123456*2; j+=i) isPrime[j]=false;
}
}
while(1){
scanf("%d",&N);
if(N == 0) break;
int result = 0;
for(int i = N+1,length=2*N; i<=length; i++){
if(isPrime[i]) result++;
}
printf("%d\n",result);
}
return 0;
}
view raw BOJ_4948.cpp hosted with ❤ by GitHub
저작자표시

'IT > 알고리즘' 카테고리의 다른 글

BOJ 백준온라인져지 1874 스택 수열 풀이  (0) 2017.11.27
BOJ 백준온라인져지 9020 골드바흐의 추측 풀이  (0) 2017.11.25
BOJ 백준온라인져지 1181 단어 정렬 풀이  (0) 2017.11.23
BOJ 백준온라인져지 1427 소트인사이드 풀이  (0) 2017.11.22
BOJ 백준온라인져지 9426 중앙값 측정 풀이  (0) 2017.11.21

+ Recent posts

티스토리툴바