Ласкаво просимо!

Ласкаво просимо вас на україномовний форум з програмування, веб-дизайну, SEO та всього пов’язаного з інтернетом та комп’ютерами.

Будемо вдячні, якщо ви поділитись посиланням на Replace.org.ua на інших ресурсах.

Для того щоб створювати теми та надсилати повідомлення вам потрібно Зареєструватись.

Сторінки 1 2 Наступна

Для відправлення відповіді ви повинні увійти або зареєструватися

Повідомлення: з 1 по 20 з 37

1 Тема від grinyuk309 09.11.2019 11:20:34

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

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

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

2 Відповідь від koala 09.11.2019 11:52:29

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

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

for(int i=2;i if(ще не визначили, чи число просте)

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

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

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

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

3 Відповідь від grinyuk309 09.11.2019 15:57:19

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

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

for(int i=2;i if(ще не визначили, чи число просте)

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

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

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

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

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

4 Відповідь від P.Y. 09.11.2019 16:13:51

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

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

5 Відповідь від grinyuk309 09.11.2019 16:18:54

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

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

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

6 Відповідь від P.Y. 09.11.2019 16:45:00

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

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

7 Відповідь від grinyuk309 09.11.2019 17:01:45

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

#include "pch.h" #include #include 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 Відповідь від koala 09.11.2019 17:37:23

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

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

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

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

9 Відповідь від grinyuk309 09.11.2019 18:26:09

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

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

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

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

#include "pch.h" #include int main() < int n; printf("Vvediti n="); scanf_s("%i", &n); int num = 0; for (int i = 1;i printf("%i", num); return 0; >

2.9: Теорема про просте число

Іншими словами, розподіл простих чисел здається досить хаотичним. Наше розуміння повної картини залишається фрагментарним, але ми збираємося побачити, що очевидний хаос у розподілі простих чисел приховує чудову закономірність трохи нижче поверхні.

Наступний пункт – це лише експеримент; але це дуже сугестивний експеримент. Це штучно, оскільки те, що вас запрошують порахувати, було ретельно підібрано, щоб вказати вам у правильному напрямку. Отримане спостереження, як правило, називають теоремою простих чисел. Результат був припущений Лежандр (1752—1833) та Гаусс (1777—1855) наприкінці 1790-х років — і був доведений 100 років потому (незалежно і майже одночасно) у 1896 році французьким математиком Адамаром (1865—1963) та бельгійським математиком де ла Валле Пуссен (1866—1962). Вам потрібно буде отримати доступ до списку простих чисел до 5000 скажімо.

Проблема 77 Нехай π ( х ) позначають кількість простих чисел ≤ х : так π ( 1 ) = 0 , π ( 2 ) = 1 , π ( 3 ) = π ( 4 ) = 2 , π ( 100 ) = 25 . Вам пропонується порахувати кількість простих чисел до певних ретельно підібраних чисел, а потім вивчати результати. Візерунок, який ви повинні помітити, працює так само добре і для інших чисел – але значно важче помітити.

Спеціальні значення, які ми вибираємо для «x», є

наступне ціле число над послідовними ступенями спеціального числа e,

де e є важливою константою в математиці — ірраціональне число, десяткове число якого починається 2.7182818 · · ·, і яке має власну кнопку на більшості калькуляторів (див. Задача 248).

(a) Заповніть наступну таблицю.

(b) Знайдіть вираз, який, здається, вказує π ( П ) як функція n. Звідси здогадка вираз для π ( х ) в перерахунку на x.

Нідерландський рослинний масив Таттоніерен.

[Через систематичне бурчання.]

Карл Фрідріх Гаусс (1777-1855),

коли його запитали, як він прийшов зробити стільки глибоких відкриттів в математиці.