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

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), который возвращает истину, если x является простым, и ложь в противном случае.

Затем, чтобы сгенерировать 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 (как в методе сита, так и в простом методе). Рассматривайте x = 2 как крайний случай, а затем начинайте проверять все остальные числа (3, 5, 7, 9, 11 и т. Д.)

Answer 3

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 включительно. Что вы собираетесь делать с этими целыми числами?

Каждый раз, когда вы проходите цикл верхнего уровня (цикл x), вы начинаете цикл a с нуля, и каждый раз, когда вы проходите цикл a, вы запускаете свой цикл *1037*. 1039 * петля с нуля.

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

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

var primes = new List<int>();

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

Answer 4

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 5

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

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 6

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

Answer 7

Как только вы разобрались с циклами, вам нужно только проверить b