0

Найдите все простые числа меньшие 𝑁. Формат входных данных: В первой строке содержатся два целых числа: 𝑁 — диапазон, в котором нужно найти все простые числа и 𝑄 — количество запросов в файле (10 <= 𝑁 <= 20 000 000, 1 <= 𝑄 <= 200 000). В каждой из следующих 𝑄 строк содержится по одному целому числу 𝑋, для которого нужно вывести, простое оно или нет (0 <= 𝑋 < 𝑛). Формат выходных данных: Нужно вывести 𝑄 ответов, по одному в каждой строке. Каждый ответ — это само число, указанное в запросе, и слово prime или not в зависимости то того, является число простым или нет.

Мой код, в принципе, работает почти правильно. Только он 0 и 1 почему-то определяет как простые числа, хотя это не так. Подскажите, что нужно подправить, пожалуйста:

#include<stdio.h>

int Simple ( int N )
{
for ( int i = 2; i*i <= N; i ++ )
if ( N % i == 0 ) return 0;
return 1;
}

int main(){
    int N, Q, i;
    scanf("%d %d", &N, &Q);
    int a[200000];
    for(int k=1; k<=Q; k++){
        scanf("%d", &a[k]);
    }
    for(int k=1; k<=Q; k++){
        if (a[k]<N){
        if ( Simple (a[k]) )
         printf ( "%d prime\n", a[k] );
        else printf ( "%d not\n", a[k] );
        getch(); }
    }
    return 0;
}

3 ответа 3

2
int Simple ( int N )
{
    for ( int i = 2; i*i <= N; i ++ )
        if ( N % i == 0 ) return 0;
    return 1;
}

Поскольку и 0, и 1 явно меньше 4 (первого значения i*i), цикл ни разу не выполняется, и вы получаете return 1.

Добавьте обработку этого частного случая -

int Simple ( int N )
{
    if (N < 2) return 0;
    for ( int i = 2; i*i <= N; i ++ )
        if ( N % i == 0 ) return 0;
    return 1;
}

Еще два замечания... Нужен ли вам int или все же unsigned int - в плане, в общем случае нужна ли проверка отрицательных чисел? У вас она все равно не работает в исходном варианте, так как условие i*i <= N всегда ложно.

Второе - можно легко ускорить код в 2 раза - ведь проверка делимости на четные числа имеет смысл только в одном случае - для 2.

В итоге -

int Simple ( unsigned int N )
{
    if (N < 2) return 0;
    if (N == 2) return 1;
    if (N%2 == 0) return 0;
    for ( unsigned int i = 3; i*i <= N; i+=2 )
        if ( N % i == 0 ) return 0;
    return 1;
}
11
  • но теперь при тестировании все числа получаются на выходе НЕ простые :(
    – A_Hatake
    17 окт 2020 в 5:47
  • код теперь, вроде, работает правильно, но теперь другая проблема... что значит Deadlock-Timeout?
    – A_Hatake
    17 окт 2020 в 5:54
  • Ой, я набирая спутал i и N... Про таймаут - это какая-то проверяющая система? Тогда, наверное, мешает getch()?
    – Harry
    17 окт 2020 в 5:57
  • Да, проверяющая система. Если убрать getch(), появляется просто Run-Time Error
    – A_Hatake
    17 окт 2020 в 6:00
  • Значит, работает медленно. Тогда сначала лучше построить таблицу всех простых.
    – Harry
    17 окт 2020 в 6:01
1

0 и 1 - это частный случай, их можно захардкодить в условии.

Ваше решение с делением хорошо, но медленное. Почему бы не воспользоваться Решетом Эратосфена?

5
  • можно и воспользоваться, но я пока не знаю как его реализовать :)
    – A_Hatake
    17 окт 2020 в 5:56
  • там в википедии полностью написан алгоритм же
    – DiD
    17 окт 2020 в 9:15
  • ru.wikipedia.org/wiki/…
    – DiD
    17 окт 2020 в 9:17
  • вам в любом случае придется воспользоваться этим способом, так как решетом найти массив простых чисел до 1 миллиарда - это меньше секунды. потом прогнать по поиску 200000 чисел - это меньше секунды. А ваш вариант повесит комп надолго.
    – DiD
    17 окт 2020 в 9:23
  • @A_Hatake деление - это самая медленная операция в математической модели компьютера.
    – DiD
    17 окт 2020 в 9:28
0

Решила проблему ленивым способом. Получилось вот так:

#include<stdio.h>

int Simple ( int N )
{
if(N==0) return 0;
if(N==1) return 0;
for ( int i = 2; i*i <= N; i ++ )
if ( N % i == 0 ) return 0;
return 1;
}

int main(){
    int N, Q, i;
    scanf("%d %d", &N, &Q);
    int a[200000];
    for(int k=1; k<=Q; k++){
        scanf("%d", &a[k]);
    }
    for(int k=1; k<=Q; k++){
        if (a[k]<N){
        if ( Simple (a[k]) )
         printf ( "%d prime\n", a[k] );
        else printf ( "%d not\n", a[k] );
        getch(); }
    }
    return 0;
}

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge you have read our privacy policy.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.