You can generate a random number and check it for a simple one and form the following if it is not simple, but it is a long process, are there any fast algorithms for generating a random simple number in C #?

  • one
    Sieve of Eratosthenes . - pank
  • one
    Issue as an answer please. Thank. - Dmitry Chistik
  • As an option, collect in a certain storage known simple numbers from the required interval and randomly choose from them. - Aleksandr Zharinov
  • @Aleksandr Zharinov I'm afraid there will be too many of them - Dmitry Chistik
  • one
    I would take increment + 2 in the cycle. All the same, the primes are odd - iRumba

2 answers 2

To search for all prime numbers in the range from 1 to n, you can use the sieve of Eratosthenes. Its description and implementation are here .

int n; vector<char> prime (n+1, true); prime[0] = prime[1] = false; for (int i=2; i<=n; ++i) if (prime[i]) if (i * 1ll * i <= n) for (int j=i*i; j<=n; j+=i) prime[j] = false;

My implementation in C # ( ideone ):

 using System; using System.Collections.Generic; public class Test { public static List<int> get_primes (int n) { bool[] is_prime = new bool[n+1]; for (int i = 2; i <= n; ++i) is_prime[i] = true; List<int> primes = new List<int>(); for (int i = 2; i <= n; ++i) if (is_prime[i]) { primes.Add(i); if (i * i <= n) for (int j=i*i; j<=n; j+=i) is_prime[j] = false; } return primes; } public static void Main() { List<int> primes = get_primes(20); Console.WriteLine(string.Join(", ", primes)); } }
  • Have you tried to build and run this code? Of course, after correcting the obvious error in the first line ... - PinkTux
  • @PinkTux, this code is for demonstration, not for launch. In this case, there is an indication that the variable n integer. - pank
  • Demonstrations of what - that a vector with more than 4 billion values ​​will not work? Then yes :) - PinkTux
  • @PinkTux, if something does not suit you, then you can correct the question by clicking the "edit" button under the answer. - pank
  • @SergeyPestov cannot, because he is not Dmitry Chistik - Pavel Mayorov

There may be two main approaches:

  1. Generate a list of prime numbers in the desired range in advance and make random samples from it.
  2. generate a random odd number and check it for simplicity.

The first method is the fastest (we do not take into account the time for generating the list, it happens once, or it may not happen at all - there are some simple lists of simple lists), but it requires some kind of storage. If we are talking about the range up to UInt32, I would have dragged along a regular binary file, clogged with 4-byte values.

Ways to generate a list of simple in a given range - in bulk (if you are too lazy to look for ready-made lists). For example (in contrast to the reduced sieve of Eratosthenes, it stores only generated simple, and not all numbers from the range in general):

 std::vector<unsigned int> primes; primes.push_back(2); for (unsigned int i = 3; i < UINT_MAX; i += 2) { if ((i > 10) && (i % 10 == 5)) { continue; } for (unsigned int j = 0; j < primes.size(); j++) { if (j * j - 1 > i) { primes.push_back(i); break; } if (i % j == 0) { break; } else { primes.push_back(i); } } }

The second is slower, but does not require any overhead. In this range, I see no reason not to use the simplest and most obvious way to check for simplicity:

 int is_prime(unsigned long n) { for(unsigned long i = 3; i * i <= n; ++i) if( !(n % i)) return 0; return 1; }

The choice of method is for the performer :)