О Prime Generation в "C" - Что не так с моим кодом? -

Question

Я третий год нерегулярный студент CS, и я только что понял, что мне нужно начать писать код.

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

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

Здесь я делюсь своим последним кодом, я намереваюсь вычислить, что когда число дает остаток от нуля, оно должно бытьэто self и 1, так что count == 2;Что не так с моей реализацией и с моим стилем генерации решения?Я надеюсь, что вы согреете меня до мира программирования, я не смог найти достаточно мотивации и смелости, чтобы углубиться в программирование.

Stdio и Math.h включены

int primegen(int down,int up)
{   
    int divisor,candidate,count=0,k;

    for(candidate=down;candidate<=up;candidate++)
    {
        for(divisor=1;divisor<=candidate;divisor++)
        {
            k=(candidate%divisor);
        }
        if (k==0) count++;
        if(count==2)
        {
            printf("%d\n", candidate);
            count=0;
        }
        else
        {
            continue;
        }
    }
}

int main()
{
    primegen(3,15);
    return 0;
}

Answer 1

Вы включаете 1 и candidate в свои candidate%divisor тесты, оба из которых всегда будут возвращать 0, поэтому каждое тестируемое число будет выглядеть простым.

Вместо этого:

for(divisor=1;divisor<=candidate;divisor++)

сделать это:

for(divisor=2;divisor<candidate;divisor++)

обновление

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

• вы проверяете результат candidate%divisor вне цикла for
• к тому времени, когда вы проверяете k, k всегда candidate%candidate или 0
• вы проверяете k только один раз, после цикла делителя
• не continue в конце цикла, это то, что происходит по умолчанию

Посмотрите, вот некоторый псевдокод для максимально простой реализации. Попробуйте найти, где ваш код отклоняется от этого:

for candidate = down to up
  // assume the candidate is primt
  prime = true

  // check all divisors from 2 to the candidate - 1, inclusive
  for divisor = 2 to candidate - 1
    if candidate % divisor == 0
      // divisor is a factor of candidate
      // candidate isn't prime, so we can stop checking
      prime = false
      break
    end if
  next divisor

  // if prime is still true, we successfully tested every number from 2..candidate
  // and found no factors
  if prime
    print "candidate {candidate} is prime!"
  end if
next candidate

Answer 2

• В вашем внутреннем цикле вы вычисляете candidate%divisor для всех делителей, но только после завершения цикла вы проверяете, следует ли увеличивать count.Таким образом, вы увеличиваете его только один раз для каждого кандидата, для последнего проверенного делителя.
• Кроме того, вы не сбрасываете count для каждого кандидата во внешнем цикле.Таким образом, вы подсчитываете найденные делители для всех кандидатов вместе, в то время как вы хотите рассчитывать для каждого кандидата в отдельности.

Answer 3

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

int primegen(unsigned int down,unsigned int up)
{   
int *ar;
int divisor,candidate,count=0,k;

for(candidate=up;candidate>=down;candidate--)
    {   count=0; 
        for(divisor=2;divisor<candidate;divisor++)
            {if (((candidate%divisor)==0)) count++; }
            if(count==0) {printf("%d\n",candidate); count=0;}

    }
}
int main()
{
primegen(3,15);
return 0;
}

Наконец-то я исправил свое решение.Основная проблема заключалась в том, что я не назначал счетчик нулю до второго цикла for.Я изменил порядок кандидатов (от большого к малому) и исправил небольшие синтаксические ошибки.

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

Answer 4

Я знаю, что ваш код предназначен только для образовательных целей, однако вы должны рассмотреть Sieve of Eratosthenes, так как он, вероятно, будет самым быстрым алгоритмом для вашей проблемы.То, что он в основном делает, это:

1. Сначала рассмотрим все простые числа чисел.
2. Начиная с 2, вы учитываете все кратные простого числа не простые.
3. Перейдите к следующему простому числу и сделайте все его кратные не простыми.

Я думаю, что вы бы лучше поняли алгоритм, прочитав это: http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes

Что касается реализации, просто используйте массив, в котором все его элементы установлены в ноль, и установите элементы от простого числа до простого числа в один.

Надеюсь, это поможет!

Answer 5

Кто-то переформатировал код для ясности из его оригинальной отправленной формы.При этом они изменили одну из трех ошибок в коде.

Первая ошибка заключалась в том, что у второго оператора for после него не было скобок.В результате тело цикла состояло только из оператора, следующего за оператором for.Из прочтения кода становится ясно, что спрашивающий предполагал, что все после второго оператора цикла будет выполняться повторно.Это не то, что происходило.

По сути, идея заключалась в следующем: для каждого числа в диапазоне попробуйте все числа от 1 до кандидата.Подсчитайте количество тех, которые его делят.Посмотрите, есть ли точно 2. Это правильный алгоритм, и ответ, который говорит, что не делить на 2, неправильный.

Однако реализация делала это: для каждого числа в диапазоне делите кандидата на каждоечисло от 1 до кандидата.Затем, после того, как вы сделали все это деление, проверьте, вышел ли последний, и если да, добавьте 1 к счетчику.Итак, происходит то, что вы на самом деле проверяете, действительно ли candidate % candidate == 0, что он всегда делает.

Вторая ошибка, это то, что счетчик сбрасывается только тогда, когда он достигает 2. Итак, что происходитявляется то, что код, для любого ввода, будет возвращать все остальные числа.Для каждого кандидата count++ происходит ровно один раз.Таким образом, он достигает 2 и сбрасывается через раз.

Третья ошибка состоит в том, что, как только самый внутренний цикл будет зафиксирован, продолжение будет делать неправильную вещь, поскольку он только продолжает самый внутренний цикл.

Answer 6

Несколько советов, которые следует иметь в виду

if(!(candidate & 0x01))
    // We know its even so we can stop

if(candidate == potential_factor)
    // We can stop

if(candidate % potential_factor == 0)
    // The potential factor IS a factor and we can stop