Тема: Заповнення масива простими числами

Завдання. Заповніть масив першими п'ятнадцятьма простими числами. Щось ніяк не можу його (завдання) красиво зробити , підкажіть як зробити це завдання не використовуючи два цикла одночасно і таких порівнянь 

if ((int)j / l == (float)j / l)
                    break;

Програма

#include <iostream>
#include <conio.h>

using namespace std;

int main()
{
    int arr[15];
    for (int i = 0, j = 2; i < 15; j++)
        {
            for (int l = 2;true; l++)
            {
                if (j == l)
                {
                    arr[i++] = j;
                    cout << arr[i - 1] << "\n";
                }
                if ((int)j / l == (float)j / l)
                    break;
            }
        }
    getch();
    return 0;
}

2 Востаннє редагувалося koala (11.09.2014 10:21:43)

Re: Заповнення масива простими числами

1. Нам треба пройти 15 чисел (1-й цикл), кожне з них в циклі перевіривши на простоту (2-й цикл). Тобто 2 цикли - необхідно і достатньо.
2. Ви перевіряєте, чи ділиться число j на число l. Для цього треба просто перевірити залишок: if( j % l == 0 )...
3. Програма вкрай неоптимальна. Для перевірки на подільність достатньо перевірити, чи не ділиться число на прості числа (раніше отримані!), не більші за корінь з цього числа. Чому тільки прості, сподіваюся, зрозуміло; чому саме за корінь? Тому що якщо число x розкладається в добуток y*z, то хоча б одне з чисел y та z має бути не більше за sqrt( x ), інакше маємо протиріччя: x = y * z > sqrt( x ) * sqrt( x ) = x, тобто x > x.
Для того, щоб не користатися зайвий раз бібліотекою cmath (за принципом YAGNI) можна виразити умову sqrt( x ) > y як  x > y * y.
4. Давайте змінним зрозумілі імена.
5. Не використовуйте нестандартні функції (знову ж YAGNI), і не запитуйте вводу без пояснень.

Коротше:

#include <iostream>

using namespace std;

int main()
{
    const int primesToFind = 15;
    int primes[ primesToFind ], 
        primesFound = 0,
        candidate = 2;
    while( primesFound < primesToFind )
    {
        bool isPrime = true; // припускаємо, що наш кандидат - просте число
        for( int i = 0; 
             ( i < primesFound ) 
               && ( primes[ i ] * primes[ i ] <= candidate ) 
               && isPrime; 
             ++i )
        {
             isPrime = ( candidate % primes[ i ] != 0 );
        }
        if( isPrime )
        {
            primes[ primesFound++ ] = candidate;
            cout << candidate << endl;
        }
        ++candidate;
    }
    cout << "Press enter to continue..." << endl;
    cin.sync();
    cin.get();
    return 0;
}

Для подальшої оптимізації можна перевіряти тільки непарні числа чи тільки числа виду 6n±1.

Подякували: Arete, Betterthanyou3

3

Re: Заповнення масива простими числами

А чому б не застосувати решето Ератосфена?

Подякували: Betterthanyou1

4

Re: Заповнення масива простими числами

Tamika_Tesla написав:

А чому б не застосувати решето Ератосфена?

Та ніхто не забороняє; але:
а) повільно;
б) вимагає багато пам'яті.

5

Re: Заповнення масива простими числами

Повільно?.. Дивно.
Але серед усіх алгоритмів пошуку - найшвидший.

6

Re: Заповнення масива простими числами

Відколи це? Найстарший - так, але який в біса найшвидший? Ну хіба на старих процесорах, де сума суттєво швидша за ділення була.

7

Re: Заповнення масива простими числами

І що, вони будуть суттєво відрізнятись? Що там, що там O(n^2).

8

Re: Заповнення масива простими числами

Насправді і там, і там O(n^2/log(n)), бо кількість простих чисел зростає приблизно як n/ln(n). Але з класичним решетом є кілька проблем - наприклад, скільки чисел треба перевірити, щоб знайти 15-е просте число? З перевіркою "в лоб" таких проблем не виникає.

Подякували: quez1

9 Востаннє редагувалося User 298 (30.09.2014 15:13:08)

Re: Заповнення масива простими числами

халявство

Допоможіть будь ласка!

1.Задано масив В(М). Навести код програми упорядкування К перших елементів (К<М) у порядку спадання їх значень методом вибору.

2.Побудувати блок-схему алгоритму вирішення першої задачі.

10 Востаннє редагувалося Logans (30.09.2014 14:10:30)

Re: Заповнення масива простими числами

hrustunka-1001 написав:

Допоможіть будь ласка!

1.Задано масив В(М). Навести код програми упорядкування К перших елементів (К<М) у порядку спадання їх значень методом вибору.

2.Побудувати блок-схему алгоритму вирішення першої задачі.

Для того, щоб вам допомогли потрібно:
  1. Створити нову тему;
  2. В темі викласти конкретно завдання;
  3. Відповідно представити якійсь вже намагання зробити це завдання;
  4. Задати конкретно питання!
А краще, просто прочитати один раз правила.

Ніхто за вас робити цього не буде!

P.S. Доречі не можу знайти картинки, яку раніше вже публікували для таких людей як ви.

Подякували: koala1

11 Востаннє редагувалося hrustunka-1001 (30.09.2014 15:21:54)

Re: Заповнення масива простими числами

Хоть приблизно поясніть як це має виглядати.
Мені потрібно виконати це завдання......а я не розумію як.....можливо хтось робив щось похоже....скиньте хоть щось

12

Re: Заповнення масива простими числами

Дайте вгадаю. Вам потрібно зробити лабораторну роботу, щоб не бути відрахованим, але ви весь семестр гуляли по дискотеках з пивом, а тепер очікуєте, що хтось раптово відірветься на елементарну задачку :)
Зуб даю, що в гуглі є тьма розв'язків задач такого типу

13 Востаннє редагувалося koala (30.09.2014 15:29:56)

Re: Заповнення масива простими числами

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

yarko написав:

Дайте вгадаю. Вам потрібно зробити лабораторну роботу, щоб не бути відрахованим, але ви весь семестр гуляли по дискотеках з пивом, а тепер очікуєте, що хтось раптово відірветься на елементарну задачку :)
Зуб даю, що в гуглі є тьма розв'язків задач такого типу

Не вгадали - ще й жовтня немає.

14

Re: Заповнення масива простими числами

я заочниця і мені ніхто нічого не пояснював......просто дали завдання
ладно.....якось сама розберусь=)

Подякували: koala, yarko2

15

Re: Заповнення масива простими числами

hrustunka-1001 написав:

я заочниця і мені ніхто нічого не пояснював......просто дали завдання
ладно.....якось сама розберусь=)

Це найкраща з можливих позицій :)
Друга - це ставити тут конкретні питання (ви ж, якщо не помітили, навіть не спитали нічого, просто завдання вивалили).
Третя - гроші.
Якщо хочете, повертайтеся до другої позиції, людей, що хочуть вчитися, тут люблять.