Programming Basics Prime numbers

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

за всичко, които се нуждаят от начин за намиране на прости числа, ето един доста лесен, за запомняне начин

int num = int.Parse(Console.ReadLine());
int counter = 0;

for (int i = 1; i <= num; i++) // Задължително трябва да има в проверката и РАВНО(=)!!!
{
if (num % i == 0)
{
counter++;
}
}
if (counter == 2)
{
Console.WriteLine($"The number {num} is Prime");
}
else
{
Console.WriteLine($"The number {num} is not Prime");
}

Здравей,

Бих могъл да предложа следните оптимизации към това решение и съответните обяснения:

1. Всичко се дели на едно
Няма нужда цикълът да започва от едно, така или иначе всяко число се дели на едно. Вместо това можем да започнем от две. Това обаче ще означава, че в проверката накрая трябва да проверим дали counter == 1.

2. Добавяне на break statement
Нека си вземем едно голямо число, например най-голямото, което може да побере типът int: int.MaxValue (или това е 2,147,483,647). Изваждам 1 от него, за да стане четно, следователно сме сигурни, че не е просто. Ако го вкараме като вход на нашата програма, вероятно ще ни изведе резултат, от който ще стане ясно, че не е просто. Но има един проблем - да се завърти над 2 милиарда пъти един цикъл, отнема време. В този случай поне няколко секунди... Но все пак ще заработи в даден момент - при i = 1, ще прибави 1 към counter, при i = 2 също, при 3, при 4 и т.н. Можем да използваме следната хитрост: ако num % i == 0, значи сме разделили числото на нещо, нали? Което означава, че то вече не е просто, така че не е необходимо да се опитваме да го делим на други числа. Така съвсем спокойно можем да сложим един break след counter++, което ще спре изпълнението на цикъла. Така дори число като 2,147,483,646 ще бъде разделено на две още в началото и това ще бъде достатъчно :)

3. Вече знаем от къде започваме, но до къде?
Ние знаем, че едно число не е просто, ако то се дели на нещо в интервала от две до себе си. Оказва се, че никога едно число не може да бъде разделено на число, което е в интервала от корен крадратен от самото число до самото число. Например 1024 -> корен квадратен от 1024 е 32. Няма такова число от 32 до 1023, което да раздели 1024. Това означава, че в нашето решение при много големи стойности можем да спестим още време, като въртим цикъла не до самото число, а до корен квадратен от него. Тъй като може резулатът от корена да е дробно число, то можем да го закръглим до следващото цяло число с Math.Ceiling().

Бих се радвал, ако тези допълнителни разяснения помогнат на някого :)

Поздрави,
Светльо