the Chec language of Eratosthenes

Asked 2 years ago, Updated 2 years ago, 20 views

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;
}

c++

2022-09-20 11:11

1 Answers

I think the centinel value has an error range.

When I set the centinel value to (int)sqrt(n)+1, it says 'Right.'


2022-09-20 11:11

If you have any answers or tips


© 2024 OneMinuteCode. All rights reserved.