Как вы генерируете определенное пользователем количество простых чисел?

Question

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

Console.Write("Please enter the number of prime numbers you would like to see:");
int numberOfPrimes = Convert.ToInt32(Console.ReadLine());

for (int x = 0; x < numberOfPrimes; x++)
{
    for (int a = 2; a <= x ; ++a)
    {
        bool prime = true;
        for (int b = 2; b < a; ++b)
        {
            if (a % b == 0)
            {
                prime = false;
            }//end if
        }//end double nested for
        if (prime == true)
        {
            Console.WriteLine(a);
        }//end if
    }//end nested for
}//end for

Answer 1

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

Причина, по которой вы получаете свои текущие результаты, заключается в том, что не каждая итерация внешнего цикла (x < numberOfPrimes) выдает результат - он пропустит довольно много итераций из-за того, как структурирован внутренний цикл.

Что вам действительно нужно сделать, это реструктурировать внутренние циклы.Ваш самый внутренний цикл работает нормально и должен обнаруживать любые простые числа.Однако ваш второй цикл должен тестировать только те числа, которые еще не были протестированы.Кроме того, он должен прекратить цикл, как только вы найдете простое число.

Answer 2

Вам следует лучше структурировать свой код, в том, как вы делаете это сейчас, действительно беспорядочно.Есть метод IsPrime(int x) который возвращает true, если x в противном случае является простым и false.

Затем, чтобы сгенерировать numberOfPrimes простые числа, вы можете сделать что-то вроде этого:

for ( int primeCount = 0, currentPrime = 2; primeCount < numberOfPrimes; ++currentPrime )
  if ( IsPrime(currentPrime) )
  {
    // do whatever you want with currentPrime, like print it
    ++primeCount;
  }

Или используйте Сито Эратосфена, что является гораздо более быстрым методом.

Чтобы выяснить, является ли число x является простым или нет, попробуйте все его факторы между 2 и Sqrt(x).Почему только Sqrt(x)?Потому что , если a*b = x, тогда x / b = a и x / a = b, Таким образом, вы бы проверили все дважды, а также проверили то, чего вам не следовало, если бы вы подошли к x / 2 или даже x.

Итак, что-то вроде этого, если вы хотите использовать IsPrime(x) функция:

// i <= Sqrt(x) <=> i * i <= x
for ( int i = 2; i * i <= x; ++i )
  if ( x % i == 0 )
    return false;

return true;

Но я предлагаю вам использовать сито Эратосфена, так как это намного быстрее.Вы также можете оптимизировать работу, чтобы не проверять четные числа, поскольку четное число никогда не бывает простым, за исключением 2 (как в методе sieve, так и в наивном методе).Рассматривайте x = 2 как крайний случай, а затем начинайте проверять все остальные числа (3, 5, 7, 9, 11 и т.д.)

Answer 3

То, что вы ищете, называется "Решето Эратосфена". Поскольку я не занимаюсь выполнением чужих домашних заданий, это единственная подсказка, которую я собираюсь вам дать.Алгоритм легко найти в Интернете.

Answer 4

Следующее простое число (x) - это число, которое не может быть разделено на все простые числа s, то есть s<=sqrt(x).Таким образом, вы можете использовать функцию, подобную

public bool CheckAndAddPrime(int number,List<int> primes)
{
    var sqrt = Math.Sqrt(number);
    foreach(var prime in primes)
    {
        if(prime>sqrt) break;
        if(number % prime == 0) return false;    
    }

    primes.Add(number);
    return true;
}

И чем вы можете получить простые числа, такие как

var primes = new List<int>();
Enumerable.Range(2,int.MaxValue).Where(x => x.CheckAndAddPrime(x,primes)).Take(YouCountOfPrimes);

Answer 5

var primes = Enumerable.Range(1, numberOfPrimes )
    .Where(x => x != 1 &&
      !Enumerable.Range2, (int)Math.Sqrt(x)).Any(y => x != y && x % y == 0));

скопировано с codethinked.com

static void Main(string[] args)
{
    foreach (int no in get_first_k_primes(10))
    {
        Console.Write(" "+no.ToString() );
    }
}

public static List<int> get_first_k_primes(int k)
{
    var primes = new List<int>();

    primes.Add(2);

    int i  = 3;


    while(primes.Count < k)
    {
        if(is_prime(i))
            primes.Add(i);

        i += 2;
    }

    return primes;
}

public static bool is_prime(int n)
{
    if (n % 2 == 0 && n != 2) return false;

    int m = (int)Math.Ceiling(Math.Sqrt(n));

    for (int i = 3; i < m; i += 2)
    {
        if (n % i == 0) return false;
    }

    return true;
}

Answer 6

1.Переименуйте ваши переменные.

Во-первых, если это домашнее задание, вы получите плохие оценки (если ваш учитель того стоит), потому что у вас бессмысленные имена переменных (да, даже numberOfPrimes является неправильным и должно быть названо requiredNumberOfPrimes.Когда я вижу эту переменную, я спрашиваю себя: "Это то, сколько он хочет, или то, сколько он нашел?").

Во-вторых, это поможет вам понять, где вы идете не так.Переменным должны быть присвоены логические имена в соответствии с тем, что они представляют.Если вы не можете объяснить, что представляют ваши переменные (напримерa & b) тогда вы, вероятно, не сможете объяснить, что вы с ними делаете.

2.Посмотрите на свои петли.

for (int x = 0; x < numberOfPrimes; x++)

Структура цикла for такова (initialise; 'should I continue?'; 'each loop do this').Поэтому в вашем цикле

• Вы продолжаете до тех пор, пока x не станет равным или большим, чем numberOfPrimes*.
• Каждый раз, когда вы проходите через цикл, вы добавляете 1 к x.

Вы уверены, что это то, что вы хотите сделать? x по-видимому, это количество найденных вами простых чисел.Так почему бы не увеличить его, когда вы находите простое число, а не когда вы запускаете цикл?

for (int a = 2; a <= x ; ++a)
for (int b = 2; b < a; ++b)

Вы смотрите на каждое целое число от 2 до x, включительно.И для каждого из этих целых чисел a, вы смотрите на каждое целое число между a и 2 включительно.Что вы собираетесь делать с этими целыми числами?

Каждый раз, когда вы проходите через свой цикл верхнего уровня (the x цикл), вы собираетесь начать свой a цикл с нуля, и каждый раз, когда вы проходите через свой a цикл, в котором вы начнете свой b цикл с нуля.

Так что , если x равно 10, вы проходите через a один раз (a = 2), затем вы снова проходите через a (a =2, a= 3), затем вы снова проходите через a (a=2, a= 3, a= 4), затем...

3.Собирайте свои результаты, а не записывайте их в консоль.

var primes = new List<int>();

Это так просто.Когда вы найдете простое, primes.Add(a);.Тогда вы знаете, сколько простых чисел вы нашли (primes.Count), вы можете использовать список простых чисел для эффективного определения следующего простого числа, и вы можете использовать список позже, если потребуется.

Answer 7

Как только вы разберетесь с циклами, вам нужно будет только проверить наличие b < sqrt(a), любой другой выше, и вы бы сначала нашли другой фактор.