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

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

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

Answer 3

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

Answer 4

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

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

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

Или использовать Sieve of Eratosthenes, который является гораздо более быстрый способ.

Чтобы выяснить, является ли число 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 5

Следующее простое число (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 6

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

copied from 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 7

1. Переименовать переменные.

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

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

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

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

структура для цикла является (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 цикла вы начнете b цикл с нуля.

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

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

var primes = new List<int>(); 

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