Member 14055344 Ответов: 4

C программа для вычисления наибольшего разрыва между простыми числами в диапазоне

может ли кто-нибудь помочь мне написать эту программу ? даже псевдокод справится с этой задачей.
эта программа должна сканировать число, подобное 34, и вычислять наибольший разрыв между простыми числами до 34, я имею в виду (29-23-1)=5.
Огромное спасибо!

Что я уже пробовал:

int y,x,N,large=3,small=2,b,a;
	scanf("%d",&N);

		for(y=3;y<N;++y)
		    for(x=2;x<y;++x)
		        a=y%x;

		if(a==0) break;

		else if(y>large && y>small) small=large;

		large=y;small=x;b=large-small-1;

		if(b<large-small-1)b=large-small-1;

		printf("%d",b);

4 Ответов

Рейтинг:
1

Mohibur Rashid

Вам придется написать программу самостоятельно. Но мы можем поделиться основной идеей. Давайте обсудим самый простой способ:
1. Составьте список всех простых чисел в диапазоне
2. получить разность всех простых чисел
3. Найдите максимальное значение

Рейтинг:
1

OriginalGriff

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

Попробуйте сами, возможно, вы обнаружите, что это не так сложно, как вы думаете! Начните с генерации att простых чисел в диапазоне - это относительно просто, и, вероятно, задача, которую вы уже выполняли раньше. Затем сделайте петлю между ними, ища промежутки. Следите за самым большим до сих пор и обновляйте его, когда найдете больший. После цикла у вас есть интервал, который вам нужен.

Если вы столкнетесь с конкретной проблемой, то, пожалуйста, спросите об этом, и мы сделаем все возможное, чтобы помочь. Но мы не собираемся делать все это для вас!

Рейтинг:
0

CPallini

Я бы предложил написать функцию для теста на примитивность.
Для малых чисел наивного подхода вполне достаточно

#include <stdio.h>

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

int main()
{
  unsigned max_gap = 0;
  unsigned max_gap_lower = 0;
  unsigned last_prime = 0;
  unsigned range_limit;

  printf("insert the range upper limit\n");
  if ( scanf("%u", &range_limit) != 1)
    return -1;

  unsigned n;
  for (n=2; n<range_limit; ++n)
  {
    if ( is_prime(n) )
    {
      if ( last_prime )
      {
        unsigned gap = n - last_prime;
        if ( max_gap < gap )
        {
          max_gap = gap;
          max_gap_lower = last_prime;
        }
      }
      last_prime = n;
    }
  }
  if ( max_gap )
  {
    printf("max gap is %u between %u and %u\n", max_gap -1, max_gap_lower, max_gap_lower + max_gap);
  }
  return 0;
}


Для больших чисел вы должны выбрать более эффективный алгоритм.

Rick York

Для немного большей производительности стандартный способ состоит в том, чтобы протестировать 2, затем 3, а затем пропустить 2, чтобы затем протестировать 5, 7, 9 и т. д. Есть еще больше тестов, чем необходимо, но вдвое меньше, чем если бы вы не пропустили на 2.

CPallini

Конечно, даже тест на примитивность не должен проходить через четные числа, я проглядел его. Теперь исправлено, спасибо.

Patrice T

Вы не должны были делать это изменение, теперь isprime ошибается.
вы должны проверить 2, а затем начать цикл с 3.

CPallini

Да, вы правы. Мне определенно нужно больше кофеина.
Кстати, спасибо.

Patrice T

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

Рейтинг:
0

Patrice T

Монолитные программы-плохая идея, они только усложняют вам жизнь. Как было предложено в S3, выполнение функции, обрабатывающей, является ли число простым или нет, упростит код.

    for(x=2;x<y;++x)
        a=y%x;

if(a==0) break;

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

Использование {} вопросы в C, вы должны научиться использовать их как можно скорее.
Цитата:
Я имею в виду (29-23-1)=5.

Вы уверены, что разрыв между 23 и 29 равен 5 ?
-----
Ваш код ведет себя не так, как вы ожидаете, или вы не понимаете, почему !

Существует почти универсальное решение: запускайте свой код на отладчике шаг за шагом, проверяйте переменные.
Отладчик здесь, чтобы показать вам, что делает ваш код, и ваша задача-сравнить с тем, что он должен делать.
В отладчике нет никакой магии, он не знает, что должен делать ваш код, он не находит ошибок, он просто помогает вам, показывая, что происходит. Когда код не делает того, что ожидается, вы близки к ошибке.
Чтобы увидеть, что делает ваш код: просто установите точку останова и посмотрите, как работает ваш код, отладчик позволит вам выполнять строки 1 на 1 и проверять переменные по мере их выполнения.
Отладчик - Википедия, свободная энциклопедия[^]

Освоение отладки в Visual Studio 2010 - руководство для начинающих[^]
Базовая отладка с помощью Visual Studio 2010 - YouTube[^]
1.11 — отладка программы (пошаговое выполнение и останова) | выучить C++[^]
Отладчик здесь только для того, чтобы показать вам, что делает ваш код, и ваша задача-сравнить его с тем, что он должен делать.