Выяснить, является ли число простым

@VitekNvkz · Регистрация: 08.04.2017

Author24 — интернет-сервис помощи студентам

2.Дано натуральное число. Выяснить, является ли оно простым (простым называется натуральное число, большее 1, не имеющее других делителей, кроме единицы и самого себя). Оператор цикла с параметром не использовать.

Вообще не пойму как решать. В поиске нет ничего подходящего. Циклы фор не нужен. Только вайл и ду вайл.

@Diamante · 16.02.2018, 22:55

C#

static void Main(string[] args)
        {
            var number = 31;
            Console.WriteLine(IsPrime(number));
        }
 
        private static bool IsPrime(int number)
        {
            var denom = 1;
            while (++denom < number)
            {
                if (number % denom == 0) return false;
            }
            return true;
        }

@VitekNvkz · 17.02.2018, 02:59 **[ТС]**

Этот ответ может и верен, но он находится за пределами изученных мною материалов. Нет ли какого более примитивного способа? Так же с циклом вайл или ду вайл.

@HookMan007 · 17.02.2018, 08:55

C#

static void Main(string[] args)
        {
            Console.WriteLine("Введите число");
            int number=Convert.ToInt32(Console.ReadLine());
            int counter = 2;
            while(counter<number/2+1)
            {
                if (number % counter == 0)
                {
                    Console.Write("Число не простое");
                    Console.Read();
                    return;
                }
                counter++;
            }
            Console.Write("Число простое");
            Console.Read();
        }

@europe · 01.01.2019, 00:23

С Новым годом!
Извиняюсь, что поднимаю старую тему.
Бьюсь почти день. Пробовал разные варианты решения (последний ниже) с этого форума и прочих. Компилятор все время указывает что "Превышено максимальное время работы". Подскажите, что ему (компилятору) не нравится?

А задание такое:
Входные данные
На вход программе подается натуральное число n ≤ 2*10^9. Проверьте, является ли оно простым.

Выходные данные
Выведите YES или NO в зависимости от ответа на вопрос задачи. Максимальное время работы программы на одном тесте — 0,1 секунды.

C#

    using System;
    using System.Collections.Generic;
    using System.Linq;
    using System.Text;
     
    namespace task10
    {
        class Program
        {
            static void Main(string[] args)
            {
                int number=Convert.ToInt32(Console.ReadLine());
                int counter = 2;
                while(counter<number/2+1)
                {
                    if (number % counter == 0)
                    {
                        Console.Write("NO");
                        Console.Read();
                        return;
                    }
                    counter++;
                }
                Console.Write("YES");
            }
        }
    }

@Элд Хасп · 01.01.2019, 02:58

Сообщение от europe

Пробовал разные варианты решения (последний ниже) с этого форума и прочих. Компилятор все время указывает что "Превышено максимальное время работы".

Простых методов для быстрой проверки числа на делители не существует. При увеличении числа время работы будет расти пропорционально. На этом построены многие алгоритмы шифрования. Если бы Вы придумали простой и быстрый метод проверки числа на простоту, Вы стали бы миллионером.
При усложнении метода, можно несколько ускорить проверку, но общее время всё равно останется пропорционально числу.

Один из способов ускорения.
Проверяете число на чётность, если оно нечётно, то цикл начинаете с трёх и делители проверяете только нечётные. Это даст ускорение в 2 раза.

C#

                if (number % 2 == 0) 
                {
                     Console.Write("NO");
                     return;
                }
                     
                int counter = 3;
                while(counter<number/2+1)
                {
                    if (number % counter == 0)
                    {
                        Console.Write("NO");
                        Console.Read();
                        return;
                    }
                    counter+=2;
                }
                Console.Write("YES");

@alexus5 · 01.01.2019, 09:34

europe, определите верхний предел делителя через корень от числа

C#

1
2
3

int maxDiv = (int)(Math.Floor(Math.Sqrt(number));
while(counter < maxDiv)
...

предельное ускорение (наблюдается для чисел вида prime^2) в Math.Sqrt(number)/2 раз

@europe · 01.01.2019, 12:18

alexus5, Спасибо, помогло!

@VitekNvkz 6 / 6 / 0 Регистрация: 08.04.2017 Сообщений: 18
		1
	Выяснить, является ли число простым 16.02.2018, 21:43. Показов 9518. Ответов 7 Метки a000040, prime numbers, простое число, простые числа (Все метки) 2.Дано натуральное число. Выяснить, является ли оно простым (простым называется натуральное число, большее 1, не имеющее других делителей, кроме единицы и самого себя). Оператор цикла с параметром не использовать. Вообще не пойму как решать. В поиске нет ничего подходящего. Циклы фор не нужен. Только вайл и ду вайл. 1

@VitekNvkz 6 / 6 / 0 Регистрация: 08.04.2017 Сообщений: 18
	17.02.2018, 02:59 [ТС]	3
	Этот ответ может и верен, но он находится за пределами изученных мною материалов. Нет ли какого более примитивного способа? Так же с циклом вайл или ду вайл. 1

@europe 0 / 0 / 0 Регистрация: 30.09.2016 Сообщений: 15
	01.01.2019, 12:18	8
	alexus5, Спасибо, помогло! 0