Простота набора чисел

Question

Найдите все простые числа меньшие ?. Формат входных данных: В первой строке содержатся два целых числа: ? — диапазон, в котором нужно найти все простые числа и ? — количество запросов в файле (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;
}

Answer 1

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

Answer 2

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

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

Answer 3

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

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

БЛОГ НА HUSL

Простота набора чисел

Ответы (3 шт):