Программа на C, принимающая целое число, если это Prime или не Prime - PullRequest
Новая
       42

Программа на C, принимающая целое число, если это Prime или не Prime

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

У меня на С эти программные коды полностью и работают очень хорошо, но результат не правильный. У меня есть их код источника здесь ниже. Может ли кто-нибудь помочь мне, что происходит или что я пропустил? Все желающие могут исправить этот английский или код. 

#include <stdio.h>
#include <stdlib.h>
#include <math.h>
int main (int argc, char *argv[])
{
  int n;
  int result;

  if (argc < 2)
    {
      printf ("Usage: p4 <number>\n");
    }
  n = atoi (argv[1]);

  if (n < 2)
    {
      printf ("input number should be > 1\n");
    }
  result = isprime (n);

  if (result == 1)
    printf ("%d is prime\n", n);
  else
    printf ("%d is not prime\n", n);
  return 0;
}

Я создал функцию isprime, которая возвращает true (т. Е. 1), если переданное ему целое число является простым, и false (т. Е. 0), если оно составное (т. Е. Не простое). Число является составным, если оно делится на 2 или любое нечетное число вплоть до квадратного корня самого числа, в противном случае оно является простым. После того, как я запрограммировал его, результат не соответствует ожиданиям.

Составитель: 

p4:
-Output of program (p4) is not correct for input '9872349871':
------ Yours: ------
1282415279 is not prime
---- Reference: ----
9872349871 is not prime
--------------------

Ответы [ 4 ]

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

Проблема в том, что ваш тестовый пример '9872349871' слишком велик для размещения в int (в вашей реализации / машине).

Простое исправление заключается в следующем (изменил все на long, использовал strtol для обнаружения проблем вне диапазона ):

РЕДАКТИРОВАТЬ: В зависимости от вашего компилятора, long может быть недостаточно большим для вашего образца ввода. long long действительно гарантированно будет 8 байтов, но будет работать только на компиляторах, которые хотя бы поддерживают C99.

Действительно важная часть - это проверка вашего входного значения! В противном случае ваш код не на один бит безопаснее, чем раньше. 

char *end;
long n = strtol(argv[1], &end, 10);
if(errno == ERANGE){
    printf("The number you entered is too large!\n");
    return -1;
}

Полный код: 

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

//OK, so this is a sloppy, inefficient implementation.

/*
int isprime(long n) {
   for (long i = 2; i != n; ++i)
     if (n%i == 0)
        return 0;
   return 1;
} */


// A better one:
int isprime(long n) {
   if(n <= 3)
      return n >= 2;
   if(n%2 == 0)
      return 0;

  for (long i = 3; i <= sqrt(n); i += 2)
     if (n%i == 0)
         return 0;
  return 1;
}

int main (int argc, char *argv[])
{
   if (argc < 2)
   {
       printf ("Usage: p4 <number>\n");
       return -1;
   }

   char *end;
   long n = strtol(argv[1], &end, 10);
   if(errno == ERANGE){
      printf("The number you entered is too large!\n");
      return -1;
   }
   if (n < 2)
   {
      printf ("input number should be > 1\n");
      return -1;
   }
   int result = isprime(n);

   if (result == 1)
     printf ("%ld is prime\n", n);
   else
     printf ("%ld is not prime\n", n);
   return 0;
}
0 голосов
/ 01 ноября 2018

Проблема в том, что входное значение 9872349871 слишком велико, чтобы поместиться в 32-разрядное целое число.

Вам нужно переписать программу, чтобы использовать long long вместо int (это должно дать вам 64-битное целое число), и для анализа параметра командной строки вам нужно будет переключить atoi на atoll.

Предостережение : Если ваша реализация isprime (которая не была показана в вопросе) избегает проверки квадратного корня (a <= sqrt(b)) путем умножения значения на себя (a*a <= b), то значение в квадрате может выходить за пределы даже 64-разрядного целого числа. Таким образом, вам может потребоваться пересмотреть эту функцию, например, с a <= b/a.

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

Проблема в том, что число 9872349871 очень большое - слишком большое, чтобы поместиться в int. Когда вы конвертируете его из строки в int, он усекается, и вместо этого вы получаете 1282415279.

Это легко увидеть, если перевести числа в шестнадцатеричные числа ...

9872349871 - это 24c701aaf в шестнадцатеричном формате

1282415279 - это 4c701aaf в шестнадцатеричном формате

Таким образом, вместо использования int для вашего n и внутри вашей функции isprime вы должны использовать что-то, что может принимать большие числа, например long

long n = strtol(argv[1], &p, 10);

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

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

Могут работать следующие code: 

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

int isprime(long long n) {
    for (long long i = 2; i != n; ++i)
        if (n%i == 0)
            return 0;
    return 1;
}

int main (int argc, char *argv[])
{
    if (argc < 2)
    {
        printf ("Usage: p4 <number>\n");
        return -1;
    }
    char* p;
    long long n = strtoll(argv[1], &p, 10);
    if (n < 2 || *p != '\0')
    {
        printf ("input wrong\n");
        return -1;
    }
    int result = isprime(n);

    if (result == 1)
        printf ("%lld is prime\n", n);
    else
        printf ("%lld is not prime\n", n);
    return 0;
}
...