The source is Baekjun question 1929! Issue: Write a program that outputs all prime numbers from M to N.
Enter: In the first line, the natural numbers M and N are given with spaces between them. (1 M M N N 1,000 1,000,000) Only inputs with one or more decimals M to N are given.
Output: Outputs decimal numbers in increasing order, one per line. There is no runtime error, but when I submit it, it just says it's wrong. I googled it up to 1000 and checked that it works without a problem, and if there's a problem, it's probably from the number after that ,, ㅠㅜ I would appreciate it if you could point out any unusual cases or codes.!
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include<stdlib.h>
#include<math.h>
#include <time.h>
int main(void)
{
clock_t start, end;
double result;
intm, n; // start and end numbers are entered.
scanf("%d %d", &m, &n);
int size = n - m + 1;
int* eratosthenes = (int*)malloc(sizeof(int) *size); // Store all numbers above m and below n first.
It is only necessary to erase the multiple of the square root of int centinel = (int)sqrt(n); // n.
int flag = 0;
start = clock(); // Start time measurement
for (int i = m, j = 0; i <= n, j < size; i++, j++)
{
eratosthenes[j] = i;
}
Remove for (inti = 2; i <= centinel; i++) // from multiples of end.
{
If ((i%2 == 0 || i%3 == 0) &&flag > 3) // If it is a multiple of 2 it has already been removed and does not need to be removed.
//The case of erasing the case of 2 and 3 using the variable flag is excluded.
{
continue;
}
for (int j = 0; j < size; j++)
{
If (erratosthenes[j] == 1) // 1 is not a prime number, so remove it.
{
eratosthenes[j] = 0;
}
If (erratosthenes[j] == 0) // If the number is already erased, pass through continue because there is no need to erase it.
{
continue;
}
If (eratosthenes[j] %i == 0 &&eratosthenes[j]! = i) // Remove the multiples from the multiples of the end.
{
eratosthenes[j] = 0;
}
}
flag++;
}
end = clock(); // Time measurement end
for (int i = 0; i < size; i++)
{
If (erratosthenes[i]!=0) // outputs the numbers stored in the uneratosthenes.
{
printf("%d\n", eratosthenes[i]);
}
}
result = (double)(end - start);
printf("%lf", result);
free(eratosthenes);
return 0;
}
I think the centinel value has an error range.
When I set the centinel value to (int)sqrt(n)+1, it says 'Right.'
© 2024 OneMinuteCode. All rights reserved.