Нахождение наибольшего простого числа в введенном пользователем числе - C

Question

У меня проблема с моим кодом.Тема состоит в том, чтобы написать программу на C, которая находит наибольшее простое число в числе, введенном пользователем.

Пример: введите число: 46656665326

Вывод: 66566653

Этомой код:

#include <stdio.h>
#include <stdlib.h>

int is_prime(unsigned long long a)
{
    if(a<=1)
        return 0;
    if(a==2)
        return 1;
    for(unsigned long long p=2; p<a; p++)
        if(a%p==0)
            return 0;
    return 1;
}

unsigned long long find_largest_prime_number(unsigned long long number)
{
    unsigned long long prime=0;
    int count=0;
    unsigned long long count2=1;
    unsigned long long pom=0;
    unsigned long long pom3=0;
    pom3=number;
    while(pom3!=0)
    {
        count++;
        pom3/=10;
    }
    count++;
    int pom_1=0;
    while(pom_1<count)
    {
        count2*=10;
        pom_1++;
    }
    pom=number;
    while(count2>=10)
    {
        unsigned long long pom2=pom;
        while(pom2!=0)
        {
            if(is_prime(pom2))
                if(pom2>prime)
                    prime=pom2;
            pom2/=10;
        }
        count2/=10;
        pom=pom%count2;
    }
    return prime;
}

int main()
{
    unsigned long long x=0;
    printf("Enter number: ");
    int n1=scanf("%llu", &x);
    if(n1!=1)
    {
        printf("incorrect input");
        return 1;
    }
    printf("%llu", find_largest_prime_number(x));
    return 0;
}

Проблема в том, что он работает с максимальным 13-значным номером, но зависает, когда входной номер имеет более 13 цифр.Ex.зависает при вводе: 215911504934497

Пожалуйста, помогите, что не так с кодом?

Answer 1

Как уже упоминалось другими участниками и в комментариях, ваш код "падает" просто потому, что он неэффективен.

Многие другие участники использовали более эффективный способ проверки, является ли число простым, проверяя это число по отношению к его делителям.

ОДНАКО, это не самый эффективный способ сделать это, особенно если у вас несколько простых чисел.

Для того, чтобы сделать это еще быстрееПредлагаю реализацию Сита Эратосфена :

#define MAX_N 4294967296 //idk how big of an array your computer can actually handle. I'm using 2^32 here.

//Declare as a global variable for extra memory allocation
//unsigned char is used as it is only 1 byte (smallest possible memory alloc)
//0 for FALSE, 1 for TRUE.
unsigned char is_prime[MAX_N+1];

//Populate the is_prime function up to your input number (or MAX_N, whichever is smaller)
//This is done in O(N) time, where N is your number.
void performSieve(unsigned long long number){
    unsigned long long i,j;
    unsigned long long n = (number>MAX_N)?MAX_N:number; //quick way (ternary operator): "whichever is smaller"

    //Populating array with default as prime
    for(i=2; i<=n; i++) is_prime[i] = 1;

    for(i=4; i<=n; i+=2) is_prime[i] = 0; //all even numbers except 4 is not prime
    for(i=3; i<=n; i+=2){
        if(is_prime[i] == 1)
            for(j=i*i;j<=n;j+=i){ //all the multiples of i except i itself are NOT prime
                is_prime[i] == 0;
            }
    }    
}

//isPrime function
unsigned char isPrime(unsigned long long n){
    if(n<=1) return 0; //edge cases

    //Check if we can find the prime number in our gigantic sieve
    if(n<=MAX_N){
        return is_prime[n]; //this is O(1) time (constant time, VERY FAST!)
    }

    //Otherwise, we now use the standard "check all the divisors" method
    //with all the optimisations as suggested by previous users:
    if(n%2==0) return 0; //even number

    //This is from user @Jabberwocky
    unsigned long long limit = isqrt(a);

    for (unsigned long long p = 3; p <= limit; p += 2) {
        if (a % p == 0) return 0;
    }

    return 1;
}

Answer 2

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

int is_prime(unsigned long long a)
{
    int i=0;
    int count=0;
    int test=0;
    int limit=sqrt(a)+1;
    if(a<=1)
        return 0;
    if(a==2)
        return 1;
    if(a%2==0)
        test=1;
    else
        for(i=3; i<limit && !test; i+=2, count++)
            if(a%i==0)
                test=1;
    if(!test)
        return 1;
    else
        return 0;
}

Answer 3

Ваш код совершенно корректен.Это просто ужасно неэффективно, и поэтому требуется очень и очень много времени, чтобы выяснить, простое ли одно большое число.

Вот лучшая версия is_prime:

• Itпроверяет делители только до квадратного корня из числа проверяемого числа.
• Он проверяет только нечетные делители, если число не делится на два, бессмысленно проверять, делится ли оно на 4, 6, 8 и т. д..

---

// long long integer square root found somewhere on the internet
unsigned long long isqrt(unsigned long long x)
{
  unsigned long long op, res, one;

  op = x;
  res = 0;

  /* "one" starts at the highest power of four <= than the argument. */
  one = 1LL << 62;  /* second-to-top bit set */
  while (one > op) one >>= 2;

  while (one != 0) {
    if (op >= res + one) {
      op -= res + one;
      res += one << 1;  // <-- faster than 2 * one  
    }
    res >>= 1;
    one >>= 2;
  }
  return res;
}


int is_prime(unsigned long long a)
{
  if (a <= 1 || a == 2 || a % 2 == 0)
    return 0;

  unsigned long long count = 0;
  unsigned long long limit = isqrt(a) + 1;

  for (unsigned long long p = 3; p < limit; p += 2)
  {
    if (a % p == 0)
      return 0;
  }
  return 1;
}

Дальнейшая оптимизация, конечно, возможна.Например, также бессмысленно проверять кратность 3, если число не делилось на 3 и т. Д. Также, если вы хотите найти диапазон простых чисел, возможно, есть другие подходы, которые следует учитывать.

Answer 4

Причина блока сводится к следующему:

int is_prime(unsigned long long a)
{
    ...
    for(unsigned long long p=2; p<a; p++)
        if(a%p==0)
            return 0;
    return 1;
}

Если вы введете 215911504934497, то find_largest_prime_number вызовет is_prime(215911504934497).215911504934497 - это большое число, и выполнение a%p для каждого p от 2 до 215911504934497 стоит очень дорого (думаю, по крайней мере, вы могли бы p < a/2).Ваша программа застряла в этом цикле.Вы можете наблюдать это, выполнив простой printf внутри него:

int is_prime(unsigned long long a)
{
    ...
    for(unsigned long long p=2; p<a; p++) {
        printf("%lld %lld\n", p, a);
        if(a%p==0)
            return 0;
    }
    return 1;
}