Нахождение первого простого числа после введенного - PullRequest
Новая
       3

Нахождение первого простого числа после введенного

0 голосов
/ 16 ноября 2018

Я пытаюсь найти первое простое число после n, если не введено n уже простое число (тогда программа печатает n и завершается).

Пример ввода:

n = 7

The first prime number is: 7 (Хорошо)

n = 591

The first prime number is: 591 (Не верно, 591 нетпростое число)

n = 14

The first prime number is: 15 (Это также неверно, не должно ли быть 17?)

Где я делаю ошибку?Это может быть очевидным, но я только начинаю. 

#include <stdio.h>

int main(){

int i = 2, n, m;

printf("n = ");

do
scanf("%d", &n);
while (n < 2);

m = n / 2;

if (n == 2){
    printf("The first prime number is: %d", n);
    return 0;
}

while ( i <= m ){

    if (n % i == 0)
        n++;

        if (n % i != 0){
            printf("The first prime number is: %d", n);
            return 0;
        }   else i++;

}

return 0;
}

Ответы [ 3 ]

0 голосов
/ 16 ноября 2018

Следующие две части логики должны решить вашу проблему. 

int IsPrime(int n)
{
    int i;
    for( i=2; i <= n/i; i++)
        if( n%i == 0 ) return 0;
    return 1;
}

Эта функция достаточно быстро определяет, является ли переданное целое число простым. Прекращает тестирование после прохождения квадратного корня тестового целого числа. 

int FirstPrime(int n)
{
    while( !IsPrime(n) )
        n++;
    return n;
}

Эта функция содержит базовую логику, изложенную в вашей постановке задачи: вернуть входное значение, если оно простое, или, если это первое число после целого числа, если оно простое, не получилось.

Разбиение кода на отдельные функции значительно упрощает тестирование и анализ кода.

0 голосов
/ 19 ноября 2018

Проверка простоты

Это более простой код, который я использую для определения простых чисел: 

int isprime(unsigned number)
{
    if (number <= 1)
        return 0;
    if (number == 2 || number == 3)
        return 1;
    if (number % 2 == 0 || number % 3 == 0)
        return 0;
    for (unsigned x = 5; x * x <= number; x += 6)
    {
        if (number % x == 0 || number % (x + 2) == 0)
            return 0;
    }
    return 1;
}

Используется тот факт, что все простые числа больше 3 имеют вид 6N ± 1. Легко понять почему. Все числа форм 6N + 0, 6N + 2, 6N + 4 четко делятся на 2, а числа формы 6N + 3 явно делятся на 3, что оставляет только 6N + 1 и 6N + 5, возможно, простыми - и 6N + 5 эквивалентно 6 (N + 1) -1, поэтому формула 6N ± 1 охватывает их должным образом. Для N = 1, 6N ± 1 дает 5 и 7, которые являются простыми; N = 2 дает 11 и 13, которые являются простыми; N = 3 дает 17 и 19, которые являются простыми; N = 4 дает 23 и 25, из которых 23 простое, а 25 нет. Все простые числа больше 3 имеют форму 6N ± 1; не все числа вида 6N ± 1 простые. Все это означает, что код проверяет только два делителя из каждых шести, проходя через диапазон до квадратного корня из числа.

У меня есть более сложный вариант, который знает простые числа до 100, а затем идет каждые 6: 

int isprime(unsigned number)
{
    if (number <= 1)
        return 0;
    if (number == 2 || number == 3)
        return 1;
    if (number % 2 == 0 || number % 3 == 0)
        return 0;
    static const unsigned int small_primes[] =
    {
         5,  7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47,
        53, 59, 61, 67, 71, 73, 79, 83, 87, 89, 91, 97
    };
    enum { NUM_SMALL_PRIMES = sizeof(small_primes) / sizeof(small_primes[0]) };
    for (unsigned i = 0; i < NUM_SMALL_PRIMES; i++)
    {
        if (number == small_primes[i])
            return 1;
        if (number % small_primes[i] == 0)
            return 0;
    }
    for (unsigned i = 101; i * i <= number; i += 6)
    {
        if (number % i == 0 || number % (i + 2) == 0)
            return 0;
    }
    return 1;
}

Обычно это немного быстрее, чем другие, но только на очень небольшую величину.

Следующий штрих после

Первоначально я написал этот код для другого SO вопроса, который был удален до того, как я опубликовал ответ; он использует другой вариант isprime() с таблицей простых чисел до 1013. 

/* Inspired by the deleted question SO 5308-6674 */
/* Determine the next prime after a given number */

#include <assert.h>
#include <stdio.h>
#include <limits.h>
#include <stdbool.h>

#define NEXT_PRIME_AFTER    /* Avoid unnecessary checks in is_prime() */

#ifdef TEST
static unsigned primes[] = { 2, 3, 5, 7, 11 };
#else
static unsigned primes[] =
{
       2,    3,    5,    7,   11,   13,   17,   19,   23,   29,
      31,   37,   41,   43,   47,   53,   59,   61,   67,   71,
      73,   79,   83,   89,   97,  101,  103,  107,  109,  113,
     127,  131,  137,  139,  149,  151,  157,  163,  167,  173,
     179,  181,  191,  193,  197,  199,  211,  223,  227,  229,
     233,  239,  241,  251,  257,  263,  269,  271,  277,  281,
     283,  293,  307,  311,  313,  317,  331,  337,  347,  349,
     353,  359,  367,  373,  379,  383,  389,  397,  401,  409,
     419,  421,  431,  433,  439,  443,  449,  457,  461,  463,
     467,  479,  487,  491,  499,  503,  509,  521,  523,  541,
     547,  557,  563,  569,  571,  577,  587,  593,  599,  601,
     607,  613,  617,  619,  631,  641,  643,  647,  653,  659,
     661,  673,  677,  683,  691,  701,  709,  719,  727,  733,
     739,  743,  751,  757,  761,  769,  773,  787,  797,  809,
     811,  821,  823,  827,  829,  839,  853,  857,  859,  863,
     877,  881,  883,  887,  907,  911,  919,  929,  937,  941,
     947,  953,  967,  971,  977,  983,  991,  997, 1009, 1013,
};
#endif /* TEST */

enum { N_PRIMES = sizeof(primes) / sizeof(primes[0]) };

/*
** In the context of next_prime_after(), this function is never called
** upon to validate small numbers - numbers less than primes[N_PRIMES-1]
** are not passed here.  In more general contexts, the extra conditions
** in the conditionally compiled code are necessary for accuracy.
*/
static bool is_prime(unsigned p)
{
    for (int i = 0; i < N_PRIMES; i++)
    {
#ifndef NEXT_PRIME_AFTER
        if (p < primes[i])
            return false;
        if (p == primes[i])
            return true;
#endif /* NEXT_PRIME_AFTER */
        if (p % primes[i] == 0)
            return false;
    }
    for (unsigned t = primes[N_PRIMES - 1]; t * t <= p; t += 6)
    {
        if (p % t == 0)
            return false;
        if (p % (t + 2) == 0)
            return false;
    }
    return true;
}

static unsigned next_prime_after(unsigned start)
{
    for (int i = 0; i < N_PRIMES; i++)
    {
        if (start < primes[i])
            return primes[i];
    }
    for (unsigned x = (start + 1) / 6; x < UINT_MAX / 6; x++)
    {
        unsigned t = 6 * x - 1;
        if (t > start && is_prime(t))
            return(t);
        t += 2;
        if (t > start && is_prime(t))
            return(t);
    }
    return 0;
}

int main(void)
{
    assert((primes[N_PRIMES-1]+1) % 6 == 0);
    for (unsigned u = 0; u < 100; u++)
        printf("%3u => %3u\n", u, next_prime_after(u));
    for (unsigned t = 100, u = next_prime_after(t); u < 12345678; t = u)
        printf("%3u => %3u\n", t, (u = next_prime_after(t)));
}

Будьте осторожны с функцией isprime() здесь. Он адаптирован к этому контексту и пропускает проверки, которые были бы необходимы для универсального, основного тестера общего назначения. next_prime_after() проходит по списку известных простых чисел (если вы, вероятно, имеете дело со многими большими возможными простыми числами, вы можете добавить тест, чтобы увидеть, стоит ли вообще проходить первый цикл), а затем пройти по последовательность 6N ± 1 ищет простое число.

Тестовый код печатает следующее простое число после каждого числа от 0 до 99. После этого он проходит через простые числа до 12345701 (который является первым простым числом после 12345678). 

  0 =>   2
  1 =>   2
  2 =>   3
  3 =>   5
  4 =>   5
  5 =>   7
  6 =>   7
  7 =>  11
  8 =>  11
  9 =>  11
 10 =>  11
 11 =>  13
 12 =>  13
 13 =>  17
 14 =>  17
 15 =>  17
 16 =>  17
 17 =>  19
 18 =>  19
 19 =>  23
 20 =>  23
 21 =>  23
 22 =>  23
 23 =>  29
…
 95 =>  97
 96 =>  97
 97 => 101
 98 => 101
 99 => 101
100 => 101
101 => 103
103 => 107
107 => 109
109 => 113
113 => 127
127 => 131
…
12345581 => 12345623
12345623 => 12345637
12345637 => 12345643
12345643 => 12345647
12345647 => 12345653
12345653 => 12345701
0 голосов
/ 16 ноября 2018

Ваша логика для определения простого числа неверна.

Прежде всего вы должны написать функцию (не обязательно, но рекомендуется), чтобы проверить, является ли одно число простым. Вот код для этой функции: 

    int checkPrimeNumber(int n)
    {
        int j, flag = 1;

        for(j=2; j <= n/2; ++j)
        {
            if (n%j == 0)
            {
                flag =0;
                break;
            }
        }
        return flag;
    }

Как только вы включите функцию, ваш цикл while должен зацикливаться, пока if не найдет первое простое число, начиная с N, используя эту функцию. Ниже приведен код этой функции.

Вы также можете проверить этот ответ здесь: https://codereview.stackexchange.com/questions/71212/find-smallest-prime-number-greater-than-given-n

Добро пожаловать на сайт PullRequest, где вы можете задавать вопросы и получать ответы от других членов сообщества.

Нет похожих вопросов

...