Формула простого числа
Я пытаюсь написать функцию простого числа в C#, и мне интересно, будет ли работать следующий код. Похоже, что он работает с первыми 50 числами или около того. Я просто хочу убедиться, что он будет работать независимо от того, насколько велико число:
static bool IsPrime(int number)
{
if ((number == 2) || (number == 3) || (number == 5) || (number == 7) || (number == 9))
return true;
if ((number % 2 != 0) && (number % 3 != 0) && (number % 5 != 0) &&
(number % 7 != 0) && (number % 9 != 0) && (number % 4 != 0) &&
(number % 6 != 0))
return true;
return false;
}
13 ответов
Нет, это не сработает! Пытаться 121 = 11 * 11 например, который явно не простое число.
Для любого числа, данного вашей функции, это произведение простых чисел X1, X2, ..., Xn(где n> = 2), причем все они больше или равны 11, ваша функция вернет true. (А также, как уже говорилось, 9 не простое число).
Из википедии вы можете увидеть, что:
В математике простое число (или простое число) - это натуральное число, которое имеет ровно два различных делителя натуральных чисел: 1 и себя.
так что очень простой и наивный алгоритм проверки, является ли число простым:
public bool CalcIsPrime(int number) {
if (number == 1) return false;
if (number == 2) return true;
if (number % 2 == 0) return false; // Even number
for (int i = 2; i < number; i++) { // Advance from two to include correct calculation for '4'
if (number % i == 0) return false;
}
return true;
}
Для лучших алгоритмов проверьте здесь: тест Primality
Если вы хотите проверить свой код, выполните тест, вот тестовый пример, написанный на xunit.
[Theory]
[MemberData(nameof(PrimeNumberTestData))]
public void CalcIsPrimeTest(int number, bool expected) {
Assert.Equal(expected, CalcIsPrime(number));
}
public static IEnumerable<object[]> PrimeNumberTestData() {
yield return new object[] { 0, false };
yield return new object[] { 1, false };
yield return new object[] { 2, true };
yield return new object[] { 3, true };
yield return new object[] { 4, false };
yield return new object[] { 5, true };
yield return new object[] { 6, false };
yield return new object[] { 7, true };
yield return new object[] { 8, false };
yield return new object[] { 9, false };
yield return new object[] { 10, false };
yield return new object[] { 11, true };
yield return new object[] { 23, true };
yield return new object[] { 31, true };
yield return new object[] { 571, true };
yield return new object[] { 853, true };
yield return new object[] { 854, false };
yield return new object[] { 997, true };
yield return new object[] { 999, false };
}
Это должно быть сделано...
public static bool IsPrime(this int number)
{
return (Enumerable.Range(1,number).Where(x => number % x == 0).Count() == 2);
}
Этот подход определенно не будет работать, если только ваш оператор if явно не перечисляет все простые числа от 0 до sqrt(INT_MAX) (или эквивалент C#).
Чтобы правильно проверить на простоту, вам нужно попытаться разделить ваше число на каждое простое число меньше его квадратного корня. Алгоритм сита Эратосфена - ваш лучший выбор.
Вы, очевидно, пишете из контрафактного измерения, где 9 - простое число, поэтому я думаю, что наши ответы могут не сработать для вас. Хотя две вещи:
Функции генерации простых чисел нетривиальны, но интересны, страница Википедии - хороший стартер ( http://en.wikipedia.org/wiki/Formula_for_primes)
из (число%2!=0) следует (число%4!=0). Если вы не можете разделить на 10, то вы также не можете разделить на 100.
static List<long> PrimeNumbers = new List<long>();
static void Main(string[] args)
{
PrimeNumbers.Add(2);
PrimeNumbers.Add(3);
PrimeNumbers.Add(5);
PrimeNumbers.Add(7);
for (long i = 11; i < 10000000; i += 2)
{
if (i % 5 != 0)
if (IsPrime(i))
PrimeNumbers.Add(i);
}
}
static bool IsPrime(long number)
{
foreach (long i in PrimeNumbers)
{
if (i <= Math.Sqrt(number))
{
if (number % i == 0)
return false;
}
else
break;
}
return true;
}
Это простой код для поиска простого числа в зависимости от вашего ввода.
static void Main(string[] args)
{
String input = Console.ReadLine();
long num = Convert.ToInt32(input);
long a, b, c;
c = 2;
for(long i=3; i<=num; i++){
b = 0;
for (long j = 2; j < i ; j++) {
a = i % j;
if (a != 0) {
b = b+1;
}
else {
break;
}
}
if(b == i-2){
Console.WriteLine("{0}",i);
}
}
Console.ReadLine();
}
Есть несколько основных правил, которым вы можете следовать, чтобы проверить, является ли число простым
- Четные числа отсутствуют. Если x % 2 = 0, то оно не простое
- Все не простые числа имеют простые множители. Таким образом, вам нужно только проверить число против простых чисел, чтобы увидеть, если это факторы
- Максимально возможный коэффициент, который есть у любого числа, - это квадратный корень. Вам нужно только проверить, являются ли значения <= sqrt(number_to_check) даже делимыми.
Используя этот набор логики, следующая формула вычисляет 1 000 000 простых чисел, сгенерированных за: 134,4164416 секунд в C# в одном потоке.
public IEnumerable<long> GetPrimes(int numberPrimes)
{
List<long> primes = new List<long> { 1, 2, 3 };
long startTest = 3;
while (primes.Count() < numberPrimes)
{
startTest += 2;
bool prime = true;
for (int pos = 2; pos < primes.Count() && primes[pos] <= Math.Sqrt(startTest); pos++)
{
if (startTest % primes[pos] == 0)
{
prime = false;
}
}
if (prime)
primes.Add(startTest);
}
return primes;
}
Имейте в виду, что в алгоритме есть много возможностей для оптимизации. Например, алгоритм может быть распараллелен. Если у вас есть простое число (скажем, 51), вы можете проверить все числа вплоть до его квадрата (2601) на предмет простоты в отдельных потоках, поскольку все возможные простые факторы хранятся в списке.
Это простой
только нечетные числа простые.... так
static bool IsPrime(int number)
{
int i;
if(number==2)
return true; //if number is 2 then it will return prime
for(i=3,i<number/2;i=i+2) //i<number/2 since a number cannot be
{ //divided by more then its half
if(number%i==0) //if number is divisible by i, then its not a prime
return false;
}
return true; //the code will only reach here if control
} //is not returned false in the for loop
Тестирование на первичность - путь, но если вам нужен быстрый и грязный хак, вот что.
Если он работает недостаточно быстро, вы можете построить вокруг него класс и хранить коллекцию PrimeNumbers от вызова к вызову, а не заново заполнять ее для каждого вызова.
public bool IsPrime(int val)
{
Collection<int> PrimeNumbers = new Collection<int>();
int CheckNumber = 5;
bool divisible = true;
PrimeNumbers.Add(2);
PrimeNumbers.Add(3);
// Populating the Prime Number Collection
while (CheckNumber < val)
{
foreach (int i in PrimeNumbers)
{
if (CheckNumber % i == 0)
{
divisible = false;
break;
}
if (i * i > CheckNumber) { break; }
}
if (divisible == true) { PrimeNumbers.Add(CheckNumber); }
else { divisible = true; }
CheckNumber += 2;
}
foreach (int i in PrimeNumbers)
{
if (CheckNumber % i == 0)
{
divisible = false;
break;
}
if (i * i > CheckNumber) { break; }
}
if (divisible == true) { PrimeNumbers.Add(CheckNumber); }
else { divisible = true; }
// Use the Prime Number Collection to determine if val is prime
foreach (int i in PrimeNumbers)
{
if (val % i == 0) { return false; }
if (i * i > val) { return true; }
}
// Shouldn't ever get here, but needed to build properly.
return true;
}
На форумах ExchangeCore есть хороший код, который позволит вам сгенерировать любое число для простых чисел. Но в основном вот суть:
int primesToFind = 1000;
int[] primes = new int[primesToFind];
int primesFound = 1;
primes[0] = 2;
for(int i = 3; i < int.MaxValue() && primesFound < primesToFind; i++)
{
bool isPrime = true;
double sqrt = Math.sqrt(i);
for(int j = 0; j<primesFound && primes[j] <= sqrt; j++)
{
if(i%primes[j] == 0)
{
isPrime = false;
break;
}
}
if(isPrime)
primes[primesFound++] = i;
}
Как только этот код завершит выполнение, все простые числа будут найдены в переменной массива простых чисел.
Здесь мы должны рассмотреть фактор квадратного корня. Простое число может быть проверено, если оно не делится на любое число, меньшее значения квадратного корня любого близкого числа.
static bool isPrime(long number)
{
if (number == 1) return false;
if (number == 2) return true;
if (number % 2 == 0) return false; //Even number
long nn= (long) Math.Abs(Math.Sqrt(number));
for (long i = 3; i < nn; i += 2) {
if (number % i == 0) return false;
}
return true;
}
public static bool isPrime(int number)
{
for (int k = 2; k <= Math.Ceiling(Math.Sqrt(number)); k++)
{
if (number > k && number % k == 0)
break;
if (k >= Math.Ceiling(Math.Sqrt(number)) || number == k)
{
return true;
}
}
return false;
}
Простые числа от 0 до 1 миллиона менее чем за две десятых секунды
Только что закончил. Последнее испытание составило 0,017 секунды.
Обычный ноутбук HP. 2,1 ГГц
Это займет больше времени, когда он становится больше. Для простых чисел 1–1 млрд. Мой последний тест составил 28,6897 секунды. Это может быть быстрее в вашей программе, потому что я приводил объекты класса для получения значений параметров в моем.
Информация о методе
- Использует сито Эратосфена
- Принимает пол и потолок в качестве аргументов
- Использует массивы вместо списков для быстрой производительности
- Размер массива инициализируется в соответствии с верхней границей Россера-Шёнфельда
- Пропускает кратные 2, 5 и 7 при назначении значений
- Максимальный диапазон составляет от 0 до 2 147 483 646 (1 мин 44,499 с)
- Сильно прокомментировал
С помощью
using System;
using System.Diagnostics;
using System.Collections;
метод
private static int[] GetPrimeArray(int floor, int ceiling)
{
// Validate arguments.
if (floor > int.MaxValue - 1)
throw new ArgumentException("Floor is too high. Max: 2,147,483,646");
else if (ceiling > int.MaxValue - 1)
throw new ArgumentException("Ceiling is too high. Max: 2,147,483,646");
else if (floor < 0)
throw new ArgumentException("Floor must be a positive integer.");
else if (ceiling < 0)
throw new ArgumentException("Ceiling must be a positve integer.");
else if (ceiling < floor)
throw new ArgumentException("Ceiling cannot be less than floor.");
// This region is only useful when testing performance.
#region Performance
Stopwatch sw = new Stopwatch();
sw.Start();
#endregion
// Variables:
int stoppingPoint = (int)Math.Sqrt(ceiling);
double rosserBound = (1.25506 * (ceiling + 1)) / Math.Log(ceiling + 1, Math.E);
int[] primeArray = new int[(int)rosserBound];
int primeIndex = 0;
int bitIndex = 4;
int innerIndex = 3;
// Handle single digit prime ranges.
if (ceiling < 11)
{
if (floor <= 2 && ceiling >= 2) // Range includes 2.
primeArray[primeIndex++] = 2;
if (floor <= 3 && ceiling >= 3) // Range includes 3.
primeArray[primeIndex++] = 3;
if (floor <= 5 && ceiling >= 5) // Range includes 5.
primeArray[primeIndex++] = 5;
return primeArray;
}
// Begin Sieve of Eratosthenes. All values initialized as true.
BitArray primeBits = new BitArray(ceiling + 1, true);
primeBits.Set(0, false); // Zero is not prime.
primeBits.Set(1, false); // One is not prime.
checked // Check overflow.
{
try
{
// Set even numbers, excluding 2, to false.
for (bitIndex = 4; bitIndex < ceiling; bitIndex += 2)
primeBits[bitIndex] = false;
}
catch { } // Break for() if overflow occurs.
}
// Iterate by steps of two in order to skip even values.
for (bitIndex = 3; bitIndex <= stoppingPoint; bitIndex += 2)
{
if (primeBits[bitIndex] == true) // Is prime.
{
// First position to unset is always the squared value.
innerIndex = bitIndex * bitIndex;
primeBits[innerIndex] = false;
checked // Check overflow.
{
try
{
// Set multiples of i, which are odd, to false.
innerIndex += bitIndex + bitIndex;
while (innerIndex <= ceiling)
{
primeBits[innerIndex] = false;
innerIndex += bitIndex + bitIndex;
}
}
catch { continue; } // Break while() if overflow occurs.
}
}
}
// Set initial array values.
if (floor <= 2)
{
// Range includes 2 - 5.
primeArray[primeIndex++] = 2;
primeArray[primeIndex++] = 3;
primeArray[primeIndex++] = 5;
}
else if (floor <= 3)
{
// Range includes 3 - 5.
primeArray[primeIndex++] = 3;
primeArray[primeIndex++] = 5;
}
else if (floor <= 5)
{
// Range includes 5.
primeArray[primeIndex++] = 5;
}
// Increment values that skip multiples of 2, 3, and 5.
int[] increment = { 6, 4, 2, 4, 2, 4, 6, 2 };
int indexModulus = -1;
int moduloSkipAmount = (int)Math.Floor((double)(floor / 30));
// Set bit index to increment range which includes the floor.
bitIndex = moduloSkipAmount * 30 + 1;
// Increase bit and increment indicies until the floor is reached.
for (int i = 0; i < increment.Length; i++)
{
if (bitIndex >= floor)
break; // Floor reached.
// Increment, skipping multiples of 2, 3, and 5.
bitIndex += increment[++indexModulus];
}
// Initialize values of return array.
while (bitIndex <= ceiling)
{
// Add bit index to prime array, if true.
if (primeBits[bitIndex])
primeArray[primeIndex++] = bitIndex;
checked // Check overflow.
{
try
{
// Increment. Skip multiples of 2, 3, and 5.
indexModulus = ++indexModulus % 8;
bitIndex += increment[indexModulus];
}
catch { break; } // Break if overflow occurs.
}
}
// Resize array. Rosser-Schoenfeld upper bound of π(x) is not an equality.
Array.Resize(ref primeArray, primeIndex);
// This region is only useful when testing performance.
#region Performance
sw.Stop();
if (primeArray.Length == 0)
Console.WriteLine("There are no prime numbers between {0} and {1}",
floor, ceiling);
else
{
Console.WriteLine(Environment.NewLine);
for (int i = 0; i < primeArray.Length; i++)
Console.WriteLine("{0,10}:\t\t{1,15:#,###,###,###}", i + 1, primeArray[i]);
}
Console.WriteLine();
Console.WriteLine("Calculation time:\t{0}", sw.Elapsed.ToString());
#endregion
return primeArray;
}
Комментарии приветствуются! Особенно улучшения.