1

Тема: Як перевірити число на простоту?

Простим називається число, що має тільки два дільники – саме число й одиницю. Дано натуральне число n та послідовність натуральних чисел
a1, a2, …, an. Визначити кількість простих чисел – членів заданої послісдовності.

Можете підказати як саме перевіряти числа на простоту?? Те що я знайшов в інтернеті виглядає досить заплутано, можливо це через те, що там пояснювалось на основі інших задач. Я не прошу писати кодів, простj поясніть в чому суть таких завдань :D

2

Re: Як перевірити число на простоту?

У лоба - поділити число на все, на що воно може потенційно ділитися. Якщо на щось поділилося - складене. Якщо ні - просте.
Уточнення: "поділити" насправді означає знайти залишок від ділення, якщо він 0 - значить, ділиться.

for(int i=2;i<n;++i) //від 2, бо 1<2, до n-1, бо n-1<n
    if(a%i==0){не просте}
if(ще не визначили, чи число просте){просте}

Ідея для оптимізації №1:
не треба ділити на числа, більші за a/2, на них точно не ділитиметься
Ідея для оптимізації №2:
не треба ділити на числа, більші за корінь квадратний з a, бо якщо число ділиться на щось, більше за корінь із себе, то воно гарантовано ділиться на інше число, менше за цей корінь
Ідея для оптимізації №3:
не треба ділити на парні, достатньо перевірити, що не ділиться на 2
Ідея для оптимізації №4:
після 2 і 3 можна ділити лише на числа, що мають вигляд 6k±1
Ідея для оптимізації №5:
не треба ділити на взагалі все, достатньо лише на прості числа

Проблема: як не оптимізуй цей алгоритм, все одно виходить складність O(n^2).

Є інші алгоритми, так звані "решета" - там ідея полягає в створенні масиву і "викреслюванні" складених чисел. Решета загалом швидші, але все одно для дуже великих чисел повільні і вимагають великих масивів.
Є також складні ознаки, що дозволяють визначити, що число є складеним (але не гарантують, що число буде простим).

Оскільки у вас виникають такі питання, раджу вам взяти алгоритм "у лоба" і оптимізувати, наскільки вийде.

Подякували: leofun01, P.Y., 221VOLT, vаrіg2kо4

3

Re: Як перевірити число на простоту?

koala написав:

У лоба - поділити число на все, на що воно може потенційно ділитися. Якщо на щось поділилося - складене. Якщо ні - просте.
Уточнення: "поділити" насправді означає знайти залишок від ділення, якщо він 0 - значить, ділиться.

for(int i=2;i<n;++i) //від 2, бо 1<2, до n-1, бо n-1<n
    if(a%i==0){не просте}
if(ще не визначили, чи число просте){просте}

Ідея для оптимізації №1:
не треба ділити на числа, більші за a/2, на них точно не ділитиметься
Ідея для оптимізації №2:
не треба ділити на числа, більші за корінь квадратний з a, бо якщо число ділиться на щось, більше за корінь із себе, то воно гарантовано ділиться на інше число, менше за цей корінь
Ідея для оптимізації №3:
не треба ділити на парні, достатньо перевірити, що не ділиться на 2
Ідея для оптимізації №4:
після 2 і 3 можна ділити лише на числа, що мають вигляд 6k±1
Ідея для оптимізації №5:
не треба ділити на взагалі все, достатньо лише на прості числа

Проблема: як не оптимізуй цей алгоритм, все одно виходить складність O(n^2).

Є інші алгоритми, так звані "решета" - там ідея полягає в створенні масиву і "викреслюванні" складених чисел. Решета загалом швидші, але все одно для дуже великих чисел повільні і вимагають великих масивів.
Є також складні ознаки, що дозволяють визначити, що число є складеним (але не гарантують, що число буде простим).

Оскільки у вас виникають такі питання, раджу вам взяти алгоритм "у лоба" і оптимізувати, наскільки вийде.

В мене нічого не виходить написати, б я не розумію що нам робити в другому if і чи спочатку має бути int a=1?Можна маленьку підказку?

4

Re: Як перевірити число на простоту?

що нам робити в другому if

Власне, можна нічого не робити. Достатньо зробити булеву змінну is_simple, початково присвоїти їй значення true, а в циклі, якщо число на щось поділилося, змінити її на false. Таким чином, по завершенню циклу is_simple буде true, якщо число просте, і false, якщо має дільники.

Подякували: 221VOLT1

5

Re: Як перевірити число на простоту?

P.Y. написав:

що нам робити в другому if

Власне, можна нічого не робити. Достатньо зробити булеву змінну is_simple, початково присвоїти їй значення true, а в циклі, якщо число на щось поділилося, змінити її на false. Таким чином, по завершенню циклу is_simple буде true, якщо число просте, і false, якщо має дільники.

Тип bool  Я ще не вивчав, а отже викладач не прийме таке розв'язання, тому такий варіант рішення нажаль відпадає.

6

Re: Як перевірити число на простоту?

Не подобається bool — візьміть int і присвоюйте йому 0 заміть false, 1 замість true.

Подякували: 221VOLT1

7

Re: Як перевірити число на простоту?

#include "pch.h"
#include <locale>
#include <stdio.h>
int main()
{
    int num=1;//змінна, яка відображатиме кількість простих чисел
    int n;//кількість чисел послідовності
    setlocale(LC_CTYPE, "ukr");
    printf("Введiть n=");
    scanf_s("%i", &n);//введення останнього числа послідовності
    for (int i = 2;i < n;++i)// не можу пояснити
        for (int a = 2;a < i;++a)// не можу пояснити
    {
            if (i % a == 0)// шукаєм числа, що діляться без остачі
                break;//виходим з циклу в разі істини
            else if (i == a + 1)//не розумію чому і як, але умова знаходить прості числа
                num++;//збільшуєм на 1 якщо умова істина                
    }
    printf("%i", num);//виводим те, що ми назбільшували
    return 0;
}

Зібравши всі свої знання і те що я знайшов в інтернеті мені вдалося скласти таку програму. Проблем з роботою нема, але я хочу зрозуміти як це все працює, тому можете прокоментувати  і виправити рядки програми?

8

Re: Як перевірити число на простоту?

Ця програма не виконує заявленої дії: в умові була послідовність a1..an, а у вас - просто числа від 2 до n-1. І не користуйтеся знайденими в Інтернеті фрагментами, якщо не можете пояснити їхньої дії - якщо, звісно, ви хочете навчитися програмувати, а не здати і забути.
Спробуємо з'ясувати, із чим саме у вас проблеми. Ось трохи змінена задача:

Парним зветься число, що ділиться на 2. Дано натуральне число n та послідовність натуральних чисел a1, a2, …, an. Визначити кількість простих парних чисел – членів заданої послідовності.

Таке зможете розв'язати самостійно чи хоча б з повним розумінням коду?

Подякували: vаrіg2kо1

9

Re: Як перевірити число на простоту?

koala написав:

Ця програма не виконує заявленої дії: в умові була послідовність a1..an, а у вас - просто числа від 2 до n-1. І не користуйтеся знайденими в Інтернеті фрагментами, якщо не можете пояснити їхньої дії - якщо, звісно, ви хочете навчитися програмувати, а не здати і забути.
Спробуємо з'ясувати, із чим саме у вас проблеми. Ось трохи змінена задача:

Парним зветься число, що ділиться на 2. Дано натуральне число n та послідовність натуральних чисел a1, a2, …, an. Визначити кількість простих парних чисел – членів заданої послідовності.

Таке зможете розв'язати самостійно чи хоча б з повним розумінням коду?

#include "pch.h"
#include <iostream>

int main()
{
    int n;
    printf("Vvediti n=");
    scanf_s("%i", &n);
    int num = 0;
    for (int i = 1;i <= n;i++)
    {
        if (i % 2 == 0)
            num++;
    }
    printf("%i", num);
    return 0;
}

Чи послідовність а*1...а*n?

10

Re: Як перевірити число на простоту?

Порівняйте фрази "дано число n" та "дана послідовність натуральних чисел a1, a2, …, an".
Чому ви вважаєте, що ці фрази означають різні речі?

Подякували: 221VOLT, vаrіg2kо2

11

Re: Як перевірити число на простоту?

koala написав:

Порівняйте фрази "дано число n" та "дана послідовність натуральних чисел a1, a2, …, an".
Чому ви вважаєте, що ці фрази означають різні речі?

Ну число n це якесь одне число, а "дана послідовність натуральних чисел a1, a2, …, an" це послідовність (набір) чисел, що складається з "n" кількості цифр

12

Re: Як перевірити число на простоту?

Гм. Вам варто повторити шкільну математику. І трохи дошкільну, питання про цифри і числа було на співбесідах у перший клас.

Якщо в умові сказано, що щось "дане", то це означає, що його будуть давати кожного разу нове. Послідовні числа від 1 до n - не дані, вони визначені. Тобто в циклі треба буде робити scanf.
Тепер ми маємо код

//початок лишаємо
   for (int i = 1;i <= n;i++)
    {
        printf("Введіть a%d = ");
        scanf_s("%d",&a);
        //тут щось обчислюємо, щоб підставити в наступну умову
        if (число просте)
            num++;
    }
//кінець лишаємо

Цей код зрозумілий? Тепер лишилося вписати перевірку на простоту.

Подякували: 221VOLT, vаrіg2kо2

13

Re: Як перевірити число на простоту?

koala написав:

Гм. Вам варто повторити шкільну математику. І трохи дошкільну, питання про цифри і числа було на співбесідах у перший клас.

Якщо в умові сказано, що щось "дане", то це означає, що його будуть давати кожного разу нове. Послідовні числа від 1 до n - не дані, вони визначені. Тобто в циклі треба буде робити scanf.
Тепер ми маємо код

//початок лишаємо
   for (int i = 1;i <= n;i++)
    {
        printf("Введіть a%d = ");
        scanf_s("%d",&a);
        //тут щось обчислюємо, щоб підставити в наступну умову
        if (число просте)
            num++;
    }
//кінець лишаємо

Цей код зрозумілий? Тепер лишилося вписати перевірку на простоту.

Добре, я зрозумів різницю між ''даним'' і ''визначиним'', зрозумів що числа послідовності потрібно вводи з клавіатури, але уявлення не маю як обчислити введене число, щоб результат використати в умові. Це надто  складно для мене, або настільки просто ,що я не розглядаю це як можливий варіант рішення.

Подякували: 221VOLT1

14

Re: Як перевірити число на простоту?

grinyuk309 написав:
koala написав:

Гм. Вам варто повторити шкільну математику. І трохи дошкільну, питання про цифри і числа було на співбесідах у перший клас.

Якщо в умові сказано, що щось "дане", то це означає, що його будуть давати кожного разу нове. Послідовні числа від 1 до n - не дані, вони визначені. Тобто в циклі треба буде робити scanf.
Тепер ми маємо код

//початок лишаємо
   for (int i = 1;i <= n;i++)
    {
        printf("Введіть a%d = ");
        scanf_s("%d",&a);
        //тут щось обчислюємо, щоб підставити в наступну умову
        if (число просте)
            num++;
    }
//кінець лишаємо

Цей код зрозумілий? Тепер лишилося вписати перевірку на простоту.

Добре, я зрозумів різницю між ''даним'' і ''визначиним'', зрозумів що числа послідовності потрібно вводи з клавіатури, але уявлення не маю як обчислити введене число, щоб результат використати в умові. Це надто  складно для мене, або настільки просто ,що я не розглядаю це як можливий варіант рішення. Чи потрібно a%i та потім в умові перевіряти остачу на парність?

15

Re: Як перевірити число на простоту?

a%i потрібне для перевірки подільності числа a на число i. Якщо ділиться без остачі, результат буде 0. Якщо остача ненульова (хоч вона парна, хоч непарна) — значить, без остачі не ділиться.

16

Re: Як перевірити число на простоту?

P.Y. написав:

a%i потрібне для перевірки подільності числа a на число i. Якщо ділиться без остачі, результат буде 0. Якщо остача ненульова (хоч вона парна, хоч непарна) — значить, без остачі не ділиться.

Так, я це розумію, але навіть якщо число поділиться з ненульвою остачею то це не означає що воно просте бо деякі не прості числа теж діляться з остачею >0 чи як?

17 Востаннє редагувалося P.Y. (10.11.2019 09:53:37)

Re: Як перевірити число на простоту?

навіть якщо число поділиться з ненульвою остачею то це не означає що воно просте

Якщо число a поділиться з нульовою остачею ХОЧА Б НА ОДНЕ число i, більше за 1 і менше за нього самого, то число a НЕ просте. Якщо ЖОДНОГО випадку подільності без остачі НЕ ЗНАЙДЕНО — значить, a просте.

Подякували: 221VOLT1

18

Re: Як перевірити число на простоту?

Саме для цього і треба ділити на різні числа в циклі. Якщо не поділилося на жодне - значить просте.

Подякували: grinyuk309, 221VOLT, vаrіg2kо3

19

Re: Як перевірити число на простоту?

koala написав:

Саме для цього і треба ділити на різні числа в циклі. Якщо не поділилося на жодне - значить просте.

int main()
{
    int n,a;
    setlocale(LC_CTYPE, "ukr");
    printf("Vvediti n=");
    scanf_s("%i", &n);
    int num = 0;
    for (int i = 1;i <=n;i++)
    {
        printf("Введіть a%d = ",i);
        scanf_s("%d", &a);
        for (int j = 2;j <= a;++j)
        if (a%j != 0)
            num++;
        
    }
    printf("%i", num);
    return 0;
}

Сьогодні спитав свою вчительку ОП як зробити це завдання і не отримав ніякої відповіді, бо вона сама не знає як його зробити, і потім, коли зустріла мене на коридорі після пари, запропонувала використати вкладений цикл.  Я написав, але виводить рандомні числа

20 Востаннє редагувалося wander (12.11.2019 00:03:54)

Re: Як перевірити число на простоту?

grinyuk309 написав:
koala написав:

Саме для цього і треба ділити на різні числа в циклі. Якщо не поділилося на жодне - значить просте.

int main()
{
    int n,a;
    setlocale(LC_CTYPE, "ukr");
    printf("Vvediti n=");
    scanf_s("%i", &n);
    int num = 0;
    for (int i = 1;i <=n;i++)
    {
        printf("Введіть a%d = ",i);
        scanf_s("%d", &a);
        for (int j = 2;j <= a;++j)
        if (a%j != 0)
            num++;
        
    }
    printf("%i", num);
    return 0;
}

Сьогодні спитав свою вчительку ОП як зробити це завдання і не отримав ніякої відповіді, бо вона сама не знає як його зробити, і потім, коли зустріла мене на коридорі після пари, запропонувала використати вкладений цикл.  Я написав, але виводить рандомні числа

Гм, ви майже на фінішній прямій.
Що означає виводить рандомні числа?
Ваш коди трохи брудний, давайте його спростимо і винесемо перевірку на простоту у ф-ю.
Рішення в лоб:

bool is_prime(int const number) noexcept { 
    if (number <= 1) return false; 

    for (int i = 2; i < number; i++)
        if (number % i == 0) return false;

    return true; 
} 

Очікуємо результат
is_prime(11) true
is_prime(15) false

Тепер можна взяти послідовність чисел, скористаюсь генератором випадкових чисел, з сайту random.org
Ось, що отримав:
64  73  60  65  41  63  34  95  32  77
Занесемо це в код.

int sequence[10]{64, 73, 60, 65, 41, 63, 34, 95, 32, 77};
int count_of_prime_numbers;
for (int i = 0; i < 10; i++)
    if (is_prime(sequence[i])) count_of_prime_numbers++;

Залишається вивести count_of_prime_numbers, ну вроді відповідь має бути 2.

Подякували: 221VOLT1