It is necessary to fill an array of a given length with various primes. Here is the under-realization curve (details in the comments):

class Program { static void Main(string[] args) { int[] arr = new int[10]; Work ob = new Work(); ob.Go(arr); Console.ReadLine(); } } class Work { public void Go(int[] arr) { int temp = 2; for(int i = 0; i < arr.Length; i++) { if (i == 0) { arr[i] = temp; continue; } if (i == 1) { arr[i] = (temp = temp + 1); temp++; continue; } if ((1 == (temp / temp)) && ((temp / 1) == temp)) { //это проверка на "простое ли число" (ошибочна) не хватает условия "которое не делится без остатка ни на одно другое целое положительное число" // поэтому всё решение и разваливается. Собственно, как это реализовать??? arr[i] = temp; temp++; } } for(int j = 0; j < arr.Length; j++) { Console.WriteLine(arr[j]); } } }
  • (1 == (temp / temp)) && ((temp / 1) == temp) - and what happens differently? - Igor

6 answers 6

My five cents. :)

 class Work { public static void Go(int[] a) { int value = 1; for (int i = 0; i < a.Length; i++) { bool prime = true; do { ++value; for (int j = 0; j < i && a[j] <= value / 2 && (prime = value % a[j] != 0); ++j) ; } while (!prime); a[i] = value; } } }

Since the Go method is static, it is not necessary to create an object of class Work . It is enough to call the method as follows:

 Work.Go( arr );

For example, an array of 10 elements will be initialized by the following values

  2 3 5 7 11 13 17 19 23 29

The principle of the method is as follows. If the initial elements of the array are already filled, such as

 2 3 5 7

then in order to get the next prime number in ascending order and assign it to the next element of the array, the value of the last filled element is taken, in this case 7, increased by 1, that is, we get 8, and this number is successively divided by the previous prime numbers stored in the array. If this number is not divided completely into all the preceding prime numbers, then it means that it is a prime number. If it is divisible by one of the primes (8 is divisible by 2), then this number is again increased by 1, and the process continues until a prime number is found. For this example, such a prime number will be 11, since it is not divisible by 2, nor by 3, or by 5. It does not make sense to check its divisibility by 7 since 7 is more than 11/2 and, obviously, it will not be completely divisible by 7

  • The implementation works great. If not difficult, please add comments for a better understanding of the code. The use of such a long condition for for, as well as the value and prime variables, is not fully understood. Is it common practice to use additional variables? - Oleg
  • @ Oleg It seems to me that the algorithm of the method is so transparent that no comments are required. Nevertheless, I added a comment to my answer, although I don’t know how useful it is. - Vlad from Moscow

I propose to check the simplicity of the number, not running over all, but only on the already found prime numbers smaller than the root of x .
An example for getting the first 10 prime numbers:

 List<int> primes = new List<int> { 2, 3 }; int i = primes.Last() + 2; while (primes.Count < 10) { foreach (int p in primes) { if (i % p == 0) break; if (p * p > i) { primes.Add(i); break; } } i += 2; }

After its execution, there will be exactly 10 first prime numbers in the primes collection.

The same method, but using LINQ:

 List<int> primes = new List<int> { 2, 3 }; int i = primes.Last() + 2; while (primes.Count < 10) { int n = i; if (primes.TakeWhile(p => n % p != 0).Any(p => p * p > n)) { primes.Add(i); } i += 2; }
  • one
    The idea is good, but the division into two parts of this code I do not like. It would be better to call the function AddNextPrime and put a while loop in it. - Qwertiy ♦
  • if (i * i >= x) - brr .. It is correct here, because the remainder is checked before, but the idea itself - with equality, the number is not simple. - Qwertiy ♦
  • one
    @Qwertiy took into account your recommendations. - Dmitry D.

First, it would be better to implement the sieve of Eratosthenes.

Secondly, the test for simplicity is done something like this:

 bool IsPrime(int x) { if (x % 2 == 0) return x == 2; for (int q=3; q*q<=x; q+=2) if (x % q == 0) return false; return true; }

    stop burning processor time to calculate what has long been calculated!

     var result = new WebClient() .DownloadString("https://primes.utm.edu/lists/small/1000.txt") .Split() .SelectMany(r => {int n; return int.TryParse(r, out n) ? new int[]{n} : new int[0]; }) .Take(100).ToArray();

      It depends on what the limit and requirements for prime numbers are.

      If the numbers are very small, then you can use the search method for a complete search to the square root of the number, if up to a million, you can use the sieve of Eratosthenes .

      If you need numbers of the order of 2^32 and above, then the Miller-Rabin probability method can be used.

        Here is a relatively short LINQ version of a sequence of primes:

         static IEnumerable<int> Primes() { return Enumerable.Range(2, int.MaxValue - 2) .Where(i => ParallelEnumerable.Range(2, Math.Max(0, (int)Math.Sqrt(i) - 1)) .All(j => i % j != 0)); }