Loading...
DimitarMandarliev avatar DimitarMandarliev 2 Точки

Prime number check

        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
Programming Basics 30/06/2015 22:29:05
KatyaMarincheva avatar KatyaMarincheva 572 Точки
Best Answer

Здравей Митко,

решението използва оптимизация: ако едно число се дели на друго освен себе си и 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.

5
30/06/2015 23:15:50
DimitarMandarliev avatar DimitarMandarliev 2 Точки

Цял ден седя и го мисля. Мерси за изчерпателния отговор. Само още един въпрос: Може ли да стане с друг цикъл, не само с while?

1
DHristoskov avatar DHristoskov 211 Точки
Разбира се, че е възможно да се направи не само с "while" цикъл ето пример:
bool prime = true;
for (int divider = 2; divider <= Math.Sqrt(number); divide++)
{
         if (number % divider == 0)
         {
             prime = false;
             break;
         }
}
и още един пример с LINQ (using System.LINQ):
 
bool prime = Enumarable.Range (2, (uint)Math.Sqrt(number) - 1).All(divider => number % divider == 0);
 
Успех!!!
1
01/07/2015 12:24:40
foxvr avatar foxvr 5 Точки

Аз го направих по този начин, и при тестване ми работи. Само, че не знам до колко е вярно.

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 ");
             }

        }
    }
}

0
krum_43 avatar krum_43 756 Точки

Здравей колега,

Виждам,че си получил пълен и изчерпателен отговор.

А какъв е този тип uint или това е техническа грешка?!?

-1
22/01/2022 12:25:21
Можем ли да използваме бисквитки?
Ние използваме бисквитки и подобни технологии, за да предоставим нашите услуги. Можете да се съгласите с всички или част от тях.
Назад
Функционални
Използваме бисквитки и подобни технологии, за да предоставим нашите услуги. Използваме „сесийни“ бисквитки, за да Ви идентифицираме временно. Те се пазят само по време на активната употреба на услугите ни. След излизане от приложението, затваряне на браузъра или мобилното устройство, данните се трият. Използваме бисквитки, за да предоставим опцията „Запомни Ме“, която Ви позволява да използвате нашите услуги без да предоставяте потребителско име и парола. Допълнително е възможно да използваме бисквитки за да съхраняваме различни малки настройки, като избор на езика, позиции на менюта и персонализирано съдържание. Използваме бисквитки и за измерване на маркетинговите ни усилия.
Рекламни
Използваме бисквитки, за да измерваме маркетинг ефективността ни, броене на посещения, както и за проследяването дали дадено електронно писмо е било отворено.