uint number = uint.Parse(Console.ReadLine());
uint divider = 2;
uint maxDivider = (uint)Math.Sqrt(number);
bool prime = true;
while (prime && (divider <= maxDivider))
{
if (number % divider == 0)
{
prime = false;
}
divider++;
}
Console.WriteLine("Prime? {0}", prime);
Някой може ли да обясни това решение, т.к. не ми е много ясно?
Здравей Митко,
решението използва оптимизация: ако едно число се дели на друго освен себе си и 1, т.е.не е просто, не е prime, то ще има поне един делител не по-голям от корен квадратен от самото число. Примери: делител на 25 е 5, което е корен квадратен от 25; делител на 4 е 2; делител на 36 е 6, 36 се дели и на 12, но отново има поне един делител <= на корен квадратен от 36.
Затова в този while loop първото условие, което поставяме е divider <= (uint)Math.Sqrt(number); (по-малък или равен на корен квадратен от самото число, и този корен е сведен до цяло число.
uint divider = 2; // това е най-малкия делител, който ще използваме
В while loop-а увеличаваме на всяко завъртане делителя: divider++, и след всяко увеличение пробваме дали числото се дели на новия делител без остатък, ако да - значи не е просто число:
if (number % divider == 0)
{
prime = false;
}
Второто условие в while loop-a обаче е да въртим докато prime = true;
Така че while loop-a се прекратява в един от два случая: или сме намерили поне един делител, който дели числото без остатък и prime = false; или сме извъртели всички числа от 2 до (uint)Math.Sqrt(number).
И в двата случая излизаме от while loop-a и печатаме, ако сме излезли защото prime = false, печатаме false, ако сме излезли преди да сме намерили делител, само защото вече divider == (uint)Math.Sqrt(number), тогава печатаме true.
Здравей колега,
Виждам,че си получил пълен и изчерпателен отговор.
А какъв е този тип uint или това е техническа грешка?!?
Цял ден седя и го мисля. Мерси за изчерпателния отговор. Само още един въпрос: Може ли да стане с друг цикъл, не само с while?
Аз го направих по този начин, и при тестване ми работи. Само, че не знам до колко е вярно.
using System;
namespace PrimeNumberCheck
{
class PrimeNumberCheck
{
static void Main()
{
Console.WriteLine("Enter a number from 0 to 100:");
int number = int.Parse(Console.ReadLine());
if (number % 2 != 1 && number % number != 1)
{
Console.WriteLine(" The number is NOT a Prime ");
}
else
{
Console.WriteLine(" The number is a Prime ");
}
}
}
}