Программа для поиска простых чисел
https://stackoverflow.com/questions/1510124
-
19-09-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianВопрос
Я хочу найти простое число между 0 и длинной переменной, но я не могу получить никаких выходных данных.
Программа заключается в
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
namespace ConsoleApplication16
{
class Program
{
void prime_num(long num)
{
bool isPrime = true;
for (int i = 0; i <= num; i++)
{
for (int j = 2; j <= num; j++)
{
if (i != j && i % j == 0)
{
isPrime = false;
break;
}
}
if (isPrime)
{
Console.WriteLine ( "Prime:" + i );
}
isPrime = true;
}
}
static void Main(string[] args)
{
Program p = new Program();
p.prime_num (999999999999999L);
Console.ReadLine();
}
}
}
Может ли кто-нибудь помочь мне и выяснить, в чем возможная ошибка в программе?
Решение
Вы можете сделать это быстрее, используя почти оптимальный пробное деление сита в одну (длинную) строку вот так:
Enumerable.Range(0, Math.Floor(2.52*Math.Sqrt(num)/Math.Log(num))).Aggregate(
Enumerable.Range(2, num-1).ToList(),
(result, index) => {
var bp = result[index]; var sqr = bp * bp;
result.RemoveAll(i => i >= sqr && i % bp == 0);
return result;
}
);
Используемая здесь аппроксимационная формула для количества простых чисел: π(x) < 1.26 x / ln(x).Нам нужно проверять только простые числа, не превышающие x = sqrt(num).
Обратите внимание, что решето Эратосфена имеет гораздо лучшую сложность времени выполнения, чем пробное деление (должно работать намного быстрее для больших num ценности при правильном применении).
Другие советы
Попробуй это:
void prime_num(long num)
{
// bool isPrime = true;
for (long i = 0; i <= num; i++)
{
bool isPrime = true; // Move initialization to here
for (long j = 2; j < i; j++) // you actually only need to check up to sqrt(i)
{
if (i % j == 0) // you don't need the first condition
{
isPrime = false;
break;
}
}
if (isPrime)
{
Console.WriteLine ( "Prime:" + i );
}
// isPrime = true;
}
}
Вам нужно только проверить нечетные делители до квадратного корня числа.Другими словами, ваш внутренний цикл должен запуститься:
for (int j = 3; j <= Math.Sqrt(i); j+=2) { ... }
Вы также можете выйти из функции, как только обнаружите, что число не простое, вам больше не нужно проверять делители (я вижу, вы уже это делаете!).
Это будет работать, только если num больше двух.
Нет
Вы можете вообще избежать Sqrt, сохраняя текущую сумму.Например:
int square_sum=1;
for (int j=3; square_sum<i; square_sum+=4*(j++-1)) {...}
Это потому, что сумма чисел 1+(3+5)+(7+9) даст вам последовательность нечетных квадратов (1,9,25 и т.д.).И поэтому j представляет собой квадратный корень из square_sum.Пока square_sum меньше чем i затем j меньше квадратного корня.
Люди упоминали пару строительных блоков, из которых можно сделать это эффективно, но на самом деле никто не собрал все кусочки воедино.Тот Самый сито Эратосфена это хорошее начало, но с ним у вас закончится память длинный прежде чем вы достигнете установленного вами предела.Однако это не значит, что это бесполезно - когда вы выполняете свой цикл, то, что вас действительно волнует, - это простые делители.Таким образом, вы можете начать с использования сита для создания базы простых делителей, а затем использовать их в цикле для проверки чисел на первичность.
Однако, когда вы пишете цикл, вы действительно НЕ хотите использовать sqrt (i) в условии цикла, как было предложено в нескольких ответах.Мы с вами знаем, что sqrt - это "чистая" функция, которая всегда выдает один и тот же ответ, если задан один и тот же входной параметр.К сожалению, компилятор ЭТОГО НЕ знает, поэтому, если использовать что-то вроде '<=Math.sqrt(x)'в условии цикла он будет повторно вычислять sqrt числа на каждой итерации цикла.
Вы можете избежать этого несколькими различными способами.Вы можете либо предварительно вычислить sqrt перед циклом и использовать предварительно вычисленное значение в условии цикла, либо вы можете действовать в другом направлении и изменить i<Math.sqrt(x) Для i*i<x.Лично я бы предварительно вычислил квадратный корень, хотя - я думаю, что это понятнее и, вероятно, немного быстрее - но это зависит от количества итераций цикла ( i*i означает, что он все еще выполняет умножение в цикле).Всего за несколько итераций, i*i как правило, это происходит быстрее.При достаточном количестве итераций потери от i*i каждая итерация превышает время выполнения sqrt оказавшись вне цикла.
Вероятно, этого достаточно для размера чисел, с которыми вы имеете дело - ограничение в 15 цифр означает, что квадратный корень равен 7 или 8 цифрам, что умещается в довольно разумном объеме памяти.С другой стороны, если вы хотите часто иметь дело с числами в этом диапазоне, возможно, вам захочется взглянуть на некоторые из более сложных алгоритмов проверки простых чисел, таких как Алгоритмы Полларда или Брента.Они более сложные (мягко говоря), но лот быстрее для больших чисел.
Существуют другие алгоритмы для еще больших чисел (квадратное сито, сито для полей с общим номером) но мы не будем сейчас вдаваться в них - они намного сложнее и действительно полезны только для работы с действительно большими числами (GNFS начинает быть полезной в диапазоне от 100 цифр).
Первый шаг: напишите метод расширения, чтобы узнать, является ли ввод простым
public static bool isPrime(this int number ) {
for (int i = 2; i < number; i++) {
if (number % i == 0) {
return false;
}
}
return true;
}
2 шаг: напишите метод, который будет печатать все простые числа от 0 до введенного числа
public static void getAllPrimes(int number)
{
for (int i = 0; i < number; i++)
{
if (i.isPrime()) Console.WriteLine(i);
}
}
Возможно, это всего лишь мое мнение, но в вашей программе есть еще одна серьезная ошибка (не говоря уже о заданном вопросе о «простых числах», на который был подробно дан ответ).
Как и остальные респонденты, я предполагаю, что это домашнее задание, которое указывает на то, что вы хотите стать разработчиком (предположительно).
Вам нужно научиться разделять свой код на части.Это не то, что вам всегда нужно делать в проекте, но полезно знать, как это сделать.
Ваш метод prime_num(long num) мог бы иметь лучшее и более описательное имя.И если предполагается найти все простые числа меньше заданного числа, он должен вернуть их в виде списка.Это упрощает разделение дисплея и функций.
Если бы он просто возвращал список IList, содержащий простые числа, вы могли бы затем отображать их в своей основной функции (возможно, вызывая другую внешнюю функцию, чтобы красиво их распечатать) или использовать их в дальнейших вычислениях.
Поэтому моя лучшая рекомендация вам — сделать что-то вроде этого:
public void main(string args[])
{
//Get the number you want to use as input
long x = number;//'number' can be hard coded or retrieved from ReadLine() or from the given arguments
IList<long> primes = FindSmallerPrimes(number);
DisplayPrimes(primes);
}
public IList<long> FindSmallerPrimes(long largestNumber)
{
List<long> returnList = new List<long>();
//Find the primes, using a method as described by another answer, add them to returnList
return returnList;
}
public void DisplayPrimes(IList<long> primes)
{
foreach(long l in primes)
{
Console.WriteLine ( "Prime:" + l.ToString() );
}
}
Даже если вы в конечном итоге будете работать где-то, где подобные меры не нужны, полезно знать, как это сделать.
РЕДАКТИРОВАТЬ_ДОБАВИТЬ: Если Уилл Несс прав, то цель вопроса состоит в том, чтобы просто вывести непрерывный поток простых чисел до тех пор, пока программа работает (нажимая Pause/Break для паузы и любую клавишу для запуска снова), без серьезной надежды на то, что кто-либо достигнет этого верхнего уровня. предел, то код должен быть написан без аргумента верхнего предела и с проверкой диапазона «истина» для первого цикла «i».С другой стороны, если вопрос заключался в том, чтобы на самом деле напечатать простые числа до определенного предела, то следующий код выполнит эту работу гораздо эффективнее, используя пробное деление только для нечетных чисел, с тем преимуществом, что он вообще не использует память. (его также можно преобразовать в непрерывный цикл, как указано выше):
static void primesttt(ulong top_number) {
Console.WriteLine("Prime: 2");
for (var i = 3UL; i <= top_number; i += 2) {
var isPrime = true;
for (uint j = 3u, lim = (uint)Math.Sqrt((double)i); j <= lim; j += 2) {
if (i % j == 0) {
isPrime = false;
break;
}
}
if (isPrime) Console.WriteLine("Prime: {0} ", i);
}
}
Во-первых, код вопроса не выдает никаких результатов, поскольку переменные его цикла являются целыми числами, а проверяемый предел представляет собой огромное длинное целое число, что означает, что цикл не может достичь предела, создавая внутренний цикл. ОТРЕДАКТИРОВАНО: при этом переменная 'j' возвращается к отрицательным числам;когда переменная 'j' возвращается к -1, тестируемое число не проходит тест на простое число, поскольку все числа делятся на -1 без остатка. END_EDIT.Даже если бы это было исправлено, код вопроса производит очень медленный вывод, потому что он связан с 64-битным делением очень большого количества составных чисел (все четные числа плюс нечетные составные числа) на весь диапазон чисел до этого верхнего предела. число десять, возведенное в шестнадцатую степень для каждого простого числа, которое оно может произвести.Приведенный выше код работает, потому что он ограничивает вычисления только нечетными числами и выполняет деление по модулю только до квадратного корня. из текущего числа тестируемых.
Для отображения простых чисел до миллиарда требуется около часа, поэтому можно представить, сколько времени потребуется, чтобы отобразить все простые числа до десяти тысяч триллионов (10 в шестнадцатой степени), особенно если вычисления становятся медленнее. с увеличением дальности. END_EDIT_ADD
Хотя однострочный (своего рода) ответ @SLaks с использованием Linq работает, на самом деле это не решето Эратосфена, поскольку это просто неоптимизированная версия Судебный отдел, неоптимизированный тем, что не исключает нечетные простые числа, не начинается с квадрата найденного базового простого числа и не прекращает отбраковку базовых простых чисел, превышающих квадратный корень из верхнего числа для просеивания.Это также довольно медленно из-за множества вложенных операций перечисления.
На самом деле это злоупотребление методом Linq Aggregate и неэффективное использование первого из двух сгенерированных Linq Range.Он может стать оптимизированным испытательным отделом с меньшими накладными расходами на перечисление следующим образом:
static IEnumerable<int> primes(uint top_number) {
var cullbf = Enumerable.Range(2, (int)top_number).ToList();
for (int i = 0; i < cullbf.Count; i++) {
var bp = cullbf[i]; var sqr = bp * bp; if (sqr > top_number) break;
cullbf.RemoveAll(c => c >= sqr && c % bp == 0);
} return cullbf; }
который работает во много раз быстрее, чем ответ SLaks.Однако он по-прежнему медленный и требует много памяти из-за генерации списка и множественных перечислений, а также операций множественного деления (подразумеваемых по модулю).
Следующая истинная реализация Решета Эратосфена работает примерно в 30 раз быстрее и требует гораздо меньше памяти, поскольку она использует только однобитовое представление для каждого просеянного числа и ограничивает его перечисление выходными данными конечной последовательности итератора, а также имеет оптимизацию обработки только нечетных составных чисел: и отбирать только квадраты базовых простых чисел для базовых простых чисел до квадратного корня из максимального числа следующим образом:
static IEnumerable<uint> primes(uint top_number) {
if (top_number < 2u) yield break;
yield return 2u; if (top_number < 3u) yield break;
var BFLMT = (top_number - 3u) / 2u;
var SQRTLMT = ((uint)(Math.Sqrt((double)top_number)) - 3u) / 2u;
var buf = new BitArray((int)BFLMT + 1,true);
for (var i = 0u; i <= BFLMT; ++i) if (buf[(int)i]) {
var p = 3u + i + i; if (i <= SQRTLMT) {
for (var j = (p * p - 3u) / 2u; j <= BFLMT; j += p)
buf[(int)j] = false; } yield return p; } }
Приведенный выше код вычисляет все простые числа до десяти миллионов примерно за 77 миллисекунд на Intel i7-2700K (3,5 ГГц).
Любой из двух статических методов можно вызвать и протестировать с помощью операторов using и статического метода Main следующим образом:
using System;
using System.Collections;
using System.Collections.Generic;
using System.Linq;
static void Main(string[] args) {
Console.WriteLine("This program generates prime sequences.\r\n");
var n = 10000000u;
var elpsd = -DateTime.Now.Ticks;
var count = 0; var lastp = 0u;
foreach (var p in primes(n)) { if (p > n) break; ++count; lastp = (uint)p; }
elpsd += DateTime.Now.Ticks;
Console.WriteLine(
"{0} primes found <= {1}; the last one is {2} in {3} milliseconds.",
count, n, lastp,elpsd / 10000);
Console.Write("\r\nPress any key to exit:");
Console.ReadKey(true);
Console.WriteLine();
}
который покажет количество простых чисел в последовательности до предела, последнее найденное простое число и время, затраченное на перебор до этого момента.
РЕДАКТИРОВАТЬ_ДОБАВИТЬ: Однако для того, чтобы произвести перечисление количества простых чисел менее десяти тысяч триллионов (десять в шестнадцатой степени), как задается в вопросе, требуется сегментированный страничный подход с использованием многоядерной обработки, но даже с C++ и очень оптимизированный PrimeSieve, для этого потребуется более 400 часов, чтобы просто получить количество найденных простых чисел, и в десятки раз больше времени, чтобы перечислить их все, так что более года, чтобы сделать то, что задает вопрос.Чтобы сделать это с использованием неоптимизированного алгоритма Пробного разделения, потребуются суперэоны и очень-очень много времени, даже с использованием оптимизированного алгоритма Пробного разделения, примерно от десяти до двух миллионов лет (это два миллиона нулевых лет!! !).
Неудивительно, что его настольный компьютер просто остановился, когда он попробовал это сделать!!!!Если бы он попробовал меньший диапазон, например один миллион, он все равно обнаружил бы, что это занимает несколько секунд, как это реализовано.
Решения, которые я публикую здесь, также не справятся с этим, поскольку даже последнее Решето Эратосфена потребует около 640 терабайт памяти для этого диапазона.
Вот почему только подход с сегментированием страниц, такой как подход PrimeSieve, может решить такого рода проблемы для заданного диапазона вообще, и даже это требует очень долгого времени, от недель до лет, если у вас нет доступа к суперкомпьютеру с сотни тысяч ядер. END_EDIT_ADD
Пахнет домашней работой.В моем очень-очень старом графическом калькуляторе была такая программа.Технически цикл проверки внутреннего деления должен выполняться только до i^(1/2).Вам нужно найти «все» простые числа от 0 до L?Другая серьезная проблема заключается в том, что переменные вашего цикла имеют тип «int», а входные данные — «длинные», это приведет к переполнению, из-за которого ваши циклы не смогут выполниться ни разу.Исправьте переменные цикла.
Однострочный код на C#: -
Console.WriteLine(String.Join(Environment.NewLine,
Enumerable.Range(2, 300)
.Where(n => Enumerable.Range(2, (int)Math.Sqrt(n) - 1)
.All(nn => n % nn != 0)).ToArray()));
Тот Самый Сито Эратосфена приведенный выше ответ не совсем корректен.Как написано, он найдет все простые числа от 1 до 1000000.Чтобы найти все простые числа от 1 до num, используйте:
private static IEnumerable Primes01(int num)
{
return Enumerable.Range(1, Convert.ToInt32(Math.Floor(Math.Sqrt(num))))
.Aggregate(Enumerable.Range(1, num).ToList(),
(result, index) =>
{
result.RemoveAll(i => i > result[index] && i%result[index] == 0);
return result;
}
);
}
Начальное значение агрегата должно быть в диапазоне от 1 до num, поскольку этот список будет содержать окончательный список простых чисел.Тот Самый Enumerable.Range(1, Convert.ToInt32(Math.Floor(Math.Sqrt(num)))) это количество раз, когда семя очищается.
Форумы ExchangeCore В списке есть хорошее консольное приложение, которое предназначено для записи найденных простых чисел в файл. Похоже, вы также можете использовать этот же файл в качестве отправной точки, чтобы вам не приходилось перезапускать поиск простых чисел из 2, и они обеспечивают загрузку этого файла со всеми найденными простыми числами до 100 миллионов, так что это было бы хорошее начало.
Алгоритм на странице также использует несколько сокращений (нечетные числа и проверка только до квадратного корня), что делает его чрезвычайно эффективным и позволяет вычислять длинные числа.
так что это в основном всего две опечатки, один, самый несчастный, for (int j = 2; j <= num; j++) что является причиной непродуктивного тестирования 1%2,1%3 ... 1%(10^15-1) это продолжается очень долго, поэтому ОП не попал "любой вывод". Это должно было быть j < i; вместо. Другой, второстепенный по сравнению с этим, заключается в том, что i должно начинаться с 2, а не с 0:
for( i=2; i <= num; i++ )
{
for( j=2; j < i; j++ ) // j <= sqrt(i) is really enough
....
Конечно, этого нельзя разумно ожидать от распечатка консоли из 28 триллионов простых чисел или около того, которые необходимо завершить в любой разумный период времени.Итак, первоначальная цель задачи, очевидно, заключалась в том, чтобы распечатать постоянный поток простых чисел, на неопределенный срок.Следовательно, все решения, предлагающие простое использование решета Эратосфена, здесь совершенно бесполезны, потому что простой решето Эратосфена ограничено — предел должен быть установлен заранее.
Что здесь может сработать, так это оптимизированное пробное деление, которое будет сохранять простые числа по мере их обнаружения и проверять их на соответствие простым числам, а не только всем числам ниже кандидата.
Вторая альтернатива, с гораздо большей сложностью (т.е.гораздо быстрее) заключается в использовании сегментированное решето Эратосфена.Который является инкрементным и неограниченным.
Обе эти схемы будут использовать двухэтапное производство простых чисел:можно было бы создать и сохранить простые числа для использования на другом этапе тестирования (или просеивания), намного превышающего предел первого этапа (конечно, ниже его квадрата - автоматически расширяя первый этап, поскольку второй этап будет идти дальше и далее вверх).
Честно говоря, некоторые из предлагаемых решений очень медленные и, следовательно, являются плохими предложениями.Чтобы проверить, что одно число является простым, вам понадобится оператор деления/по модулю, но для вычисления диапазона вам это не нужно.
По сути, вы просто исключаете числа, кратные ранее найденным простым числам, поскольку они (по определению) сами по себе не являются простыми числами.
Я не буду приводить полную реализацию, так как это было бы слишком просто, это подход в псевдокоде.(На моей машине фактическая реализация вычисляет все простые числа в Sytem.Int32 (2 миллиарда) за 8 секунд.
public IEnumerable<long> GetPrimes(long max)
{
// we safe the result set in an array of bytes.
var buffer = new byte[long >> 4];
// 1 is not a prime.
buffer[0] = 1;
var iMax = (long)Math.Sqrt(max);
for(long i = 3; i <= iMax; i +=2 )
{
// find the index in the buffer
var index = i >> 4;
// find the bit of the buffer.
var bit = (i >> 1) & 7;
// A not set bit means: prime
if((buffer[index] & (1 << bit)) == 0)
{
var step = i << 2;
while(step < max)
{
// find position in the buffer to write bits that represent number that are not prime.
}
}
// 2 is not in the buffer.
yield return 2;
// loop through buffer and yield return odd primes too.
}
}
Решение требует хорошего понимания побитовых операций.Но это гораздо быстрее.Вы также можете сохранить результаты на диске, если они вам понадобятся для дальнейшего использования.Результат 17 * 10^9 чисел можно сохранить в 1 ГБ, а вычисление этого набора результатов занимает максимум около 2 минут.
Я знаю, что это тихий старый вопрос, но после прочтения здесь:Решето Эратосфена вики
Вот как я написал это, понимая алгоритм:
void SieveOfEratosthenes(int n)
{
bool[] primes = new bool[n + 1];
for (int i = 0; i < n; i++)
primes[i] = true;
for (int i = 2; i * i <= n; i++)
if (primes[i])
for (int j = i * 2; j <= n; j += i)
primes[j] = false;
for (int i = 2; i <= n; i++)
if (primes[i]) Console.Write(i + " ");
}
В первом цикле мы заполняем массив логических значений значением true.
Второй цикл for начнется с 2, поскольку 1 не является простым числом, и проверит, не изменилось ли простое число, а затем присвоит false индексу j.
последний цикл мы просто печатаем, когда он является простым.
Очень похоже — из упражнения по реализации Решета Эратосфена на C#:
public class PrimeFinder
{
readonly List<long> _primes = new List<long>();
public PrimeFinder(long seed)
{
CalcPrimes(seed);
}
public List<long> Primes { get { return _primes; } }
private void CalcPrimes(long maxValue)
{
for (int checkValue = 3; checkValue <= maxValue; checkValue += 2)
{
if (IsPrime(checkValue))
{
_primes.Add(checkValue);
}
}
}
private bool IsPrime(long checkValue)
{
bool isPrime = true;
foreach (long prime in _primes)
{
if ((checkValue % prime) == 0 && prime <= Math.Sqrt(checkValue))
{
isPrime = false;
break;
}
}
return isPrime;
}
}
Prime Helper очень быстрый расчет
public static class PrimeHelper
{
public static IEnumerable<Int32> FindPrimes(Int32 maxNumber)
{
return (new PrimesInt32(maxNumber));
}
public static IEnumerable<Int32> FindPrimes(Int32 minNumber, Int32 maxNumber)
{
return FindPrimes(maxNumber).Where(pn => pn >= minNumber);
}
public static bool IsPrime(this Int64 number)
{
if (number < 2)
return false;
else if (number < 4 )
return true;
var limit = (Int32)System.Math.Sqrt(number) + 1;
var foundPrimes = new PrimesInt32(limit);
return !foundPrimes.IsDivisible(number);
}
public static bool IsPrime(this Int32 number)
{
return IsPrime(Convert.ToInt64(number));
}
public static bool IsPrime(this Int16 number)
{
return IsPrime(Convert.ToInt64(number));
}
public static bool IsPrime(this byte number)
{
return IsPrime(Convert.ToInt64(number));
}
}
public class PrimesInt32 : IEnumerable<Int32>
{
private Int32 limit;
private BitArray numbers;
public PrimesInt32(Int32 limit)
{
if (limit < 2)
throw new Exception("Prime numbers not found.");
startTime = DateTime.Now;
calculateTime = startTime - startTime;
this.limit = limit;
try { findPrimes(); } catch{/*Overflows or Out of Memory*/}
calculateTime = DateTime.Now - startTime;
}
private void findPrimes()
{
/*
The Sieve Algorithm
http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes
*/
numbers = new BitArray(limit, true);
for (Int32 i = 2; i < limit; i++)
if (numbers[i])
for (Int32 j = i * 2; j < limit; j += i)
numbers[j] = false;
}
public IEnumerator<Int32> GetEnumerator()
{
for (Int32 i = 2; i < 3; i++)
if (numbers[i])
yield return i;
if (limit > 2)
for (Int32 i = 3; i < limit; i += 2)
if (numbers[i])
yield return i;
}
IEnumerator IEnumerable.GetEnumerator()
{
return GetEnumerator();
}
// Extended for Int64
public bool IsDivisible(Int64 number)
{
var sqrt = System.Math.Sqrt(number);
foreach (var prime in this)
{
if (prime > sqrt)
break;
if (number % prime == 0)
{
DivisibleBy = prime;
return true;
}
}
return false;
}
private static DateTime startTime;
private static TimeSpan calculateTime;
public static TimeSpan CalculateTime { get { return calculateTime; } }
public Int32 DivisibleBy { get; set; }
}
public static void Main()
{
Console.WriteLine("enter the number");
int i = int.Parse(Console.ReadLine());
for (int j = 2; j <= i; j++)
{
for (int k = 2; k <= i; k++)
{
if (j == k)
{
Console.WriteLine("{0}is prime", j);
break;
}
else if (j % k == 0)
{
break;
}
}
}
Console.ReadLine();
}
static void Main(string[] args)
{ int i,j;
Console.WriteLine("prime no between 1 to 100");
for (i = 2; i <= 100; i++)
{
int count = 0;
for (j = 1; j <= i; j++)
{
if (i % j == 0)
{ count=count+1; }
}
if ( count <= 2)
{ Console.WriteLine(i); }
}
Console.ReadKey();
}
Вы можете использовать обычное понятие простого числа, должно быть только два множителя (один и он сам).Так сделай вот так, простой способ
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
namespace PrimeNUmber
{
class Program
{
static void FindPrimeNumber(long num)
{
for (long i = 1; i <= num; i++)
{
int totalFactors = 0;
for (int j = 1; j <= i; j++)
{
if (i % j == 0)
{
totalFactors = totalFactors + 1;
}
}
if (totalFactors == 2)
{
Console.WriteLine(i);
}
}
}
static void Main(string[] args)
{
long num;
Console.WriteLine("Enter any value");
num = Convert.ToInt64(Console.ReadLine());
FindPrimeNumber(num);
Console.ReadLine();
}
}
}
Это решение отображает все простые числа от 0 до 100.
int counter = 0;
for (int c = 0; c <= 100; c++)
{
counter = 0;
for (int i = 1; i <= c; i++)
{
if (c % i == 0)
{ counter++; }
}
if (counter == 2)
{ Console.Write(c + " "); }
}
Это самый быстрый способ вычисления простых чисел в C#.
void PrimeNumber(long number)
{
bool IsprimeNumber = true;
long value = Convert.ToInt32(Math.Sqrt(number));
if (number % 2 == 0)
{
IsprimeNumber = false;
}
for (long i = 3; i <= value; i=i+2)
{
if (number % i == 0)
{
// MessageBox.Show("It is divisible by" + i);
IsprimeNumber = false;
break;
}
}
if (IsprimeNumber)
{
MessageBox.Show("Yes Prime Number");
}
else
{
MessageBox.Show("No It is not a Prime NUmber");
}
}
class CheckIfPrime
{
static void Main()
{
while (true)
{
Console.Write("Enter a number: ");
decimal a = decimal.Parse(Console.ReadLine());
decimal[] k = new decimal[int.Parse(a.ToString())];
decimal p = 0;
for (int i = 2; i < a; i++)
{
if (a % i != 0)
{
p += i;
k[i] = i;
}
else
p += i;
}
if (p == k.Sum())
{ Console.WriteLine ("{0} is prime!", a);}
else
{Console.WriteLine("{0} is NOT prime", a);}
}
}
}
Есть несколько очень оптимальных способов реализации алгоритма.Но если вы не очень разбираетесь в математике и просто следуете определению простого числа как требованию:число, которое делится только на 1 и само на себя (и ничего более), вот простой для понимания код для положительных чисел.
public bool IsPrime(int candidateNumber)
{
int fromNumber = 2;
int toNumber = candidateNumber - 1;
while(fromNumber <= toNumber)
{
bool isDivisible = candidateNumber % fromNumber == 0;
if (isDivisible)
{
return false;
}
fromNumber++;
}
return true;
}
Поскольку каждое число делится на 1 и само на себя, мы начинаем проверку с 2 и далее до числа, которое находится непосредственно перед самим собой.Это основное рассуждение.
Вы также можете сделать это:
class Program
{
static void Main(string[] args)
{
long numberToTest = 350124;
bool isPrime = NumberIsPrime(numberToTest);
Console.WriteLine(string.Format("Number {0} is prime? {1}", numberToTest, isPrime));
Console.ReadLine();
}
private static bool NumberIsPrime(long n)
{
bool retVal = true;
if (n <= 3)
{
retVal = n > 1;
} else if (n % 2 == 0 || n % 3 == 0)
{
retVal = false;
}
int i = 5;
while (i * i <= n)
{
if (n % i == 0 || n % (i + 2) == 0)
{
retVal = false;
}
i += 6;
}
return retVal;
}
}
