백준 4948 c++

https://www.acmicpc.net/problem/4948

4948번: 베르트랑 공준

 

 

문제

베르트랑 공준은 임의의 자연수 n에 대하여, n보다 크고, 2n보다 작거나 같은 소수는 적어도 하나 존재한다는 내용을 담고 있다.

이 명제는 조제프 베르트랑이 1845년에 추측했고, 파프누티 체비쇼프가 1850년에 증명했다.

예를 들어, 10보다 크고, 20보다 작거나 같은 소수는 4개가 있다. (11, 13, 17, 19) 또, 14보다 크고, 28보다 작거나 같은 소수는 3개가 있다. (17,19, 23)

자연수 n이 주어졌을 때, n보다 크고, 2n보다 작거나 같은 소수의 개수를 구하는 프로그램을 작성하시오. 

입력

입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 케이스는 n을 포함하는 한 줄로 이루어져 있다.

입력의 마지막에는 0이 주어진다.

출력

각 테스트 케이스에 대해서, n보다 크고, 2n보다 작거나 같은 소수의 개수를 출력한다.

제한

• 1 ≤ n ≤ 123,456

 

 

 

 

일단 n을 입력받고 n과 2n사이의값의 보수들을 출력을 하는 코드를 짜고...

그 보수들을 배열로 만들어서 길이를 출력하면 되겠는데?

 

 

 

 

 

작성코드

 

 

#include <iostream>

using namespace std;

int main() {

int n;

dec[123456];

cnt = 0;

cin>>n;

 

for(i=n;i<=2n;i++)

{

dec[i] = 1;

//n부터 2n까지 1로 배열속 지정

}

 

for (i=n;i<=2n;i++)

{

for(j=1;nj<=2n;j++){

 

dec[i] = 0; //n부터 2n 사이의 모든 수의 배수를 0으로 바꾼다.

}

}

 

for(i=n;i<=2n;i++)

{

if(decp[i]==1)

{

cnt++;

}

 

}

 

 

 

}

 

 

 

 

 

 

 

 

오류제거 코드

 

 

#include <iostream>

using namespace std;

int main() {

int n;

int dec[123456]; // Fixed the declaration of dec array

int cnt = 0; // Added missing declaration for cnt variable

cin >> n;

for (int i = n; i <= 2 * n; i++) {

dec[i] = 1;

// Set values from n to 2n as 1 in the dec array

}

for (int i = n; i <= 2 * n; i++) {

for (int j = 1; j <= 2 * n; j++) { // Fixed the condition of the inner loop

dec[i] = 0; // Change all multiples of numbers from n to 2n to 0

}

}

for (int i = n; i <= 2 * n; i++) {

if (dec[i] == 1) {

cnt++;

}

}

// Code error has been fixed

return 0;

}

 

 

 

근데 왜 작동을 안할까 후...

 

 

해설을 보자

 

 

 

 

해설

 

#include <iostream>

#include <cmath>

using namespace std;

int main() {

int a[123456];

int n;

 

cin >> n;

 

int count = 0;

 

a[0] = 0;

a[1] = 0;

for (int i = 2; i <= 2 * n; i++)

a[i] = 1;

for (int i = 2; i <= int(sqrt(2 * n)); i++) {

for (int j =2; i*j <= 2*n; j++) {

a[i*j] = 0;

}

}

for (int k = n+1; k <= 2 * n; k++) {

if (a[k] == 1)

count++;

}

cout << count << '\n';

cin >> n;

 

}

 

 

 

 

 

왜 내 코드가 잘못된지 보니까 

중간에 2n 하고 제곱근을 안넣어서 숫자가 안나온거같다...

 

확인 외우자

 

 

>> 근데 왜 백준에서 틀렸다 뜨지?  자고일어나서 수정하기.

왜틀렸나 했더니 백준 입력 양식을 제대로 안지켰다. 명심하기

 

 

 

 

#include <iostream>

#include <cmath>

using namespace std;

int main() {

int a[246913];

int n;

 

cin >> n;

while (1) {

int count = 0;

 

a[0] = 0;

a[1] = 0;

for (int i = 2; i <= 2 * n; i++)

a[i] = 1;

for (int i = 2; i <= int(sqrt(2 * n)); i++) {

for (int j =2; i*j <= 2*n; j++) {

a[i*j] = 0;

}

}

for (int k = n+1; k <= 2 * n; k++) {

if (a[k] == 1)

count++;

}

cout << count << '\n';

cin >> n;

if (n == 0)

break;

}

}