Форум программистов, компьютерный форум CyberForum.ru

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
Dangelo
7 / 7 / 1
Регистрация: 28.11.2010
Сообщений: 57
#1

Простые числа. - C++

12.12.2010, 03:50. Просмотров 588. Ответов 1
Метки нет (Все метки)

Доброй ночи. Есть вот такое задание
Исходные данные
В первой строке находится ровно одно целое число k, задающее количество чисел в списке. За ним следуют k целых чисел, по одному в строке. Все числа положительные и не превосходят 15000.
Результат
Для каждого числа n из списка вы должны вывести n-е по счёту простое число. Ответ для каждого числа должен находиться в отдельной строке.
Пример
исходные данные результат
4 5
3 3
2 11
5 17
7

и такой код:
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
#include "stdafx.h"
#include <stdio.h>
unsigned  int t[170000];
unsigned int o=170000;
void mass();
void prost (int p);
void main()
{
    int k, n[15001], p;
    scanf ("%d", &k);
    for (int i=0; i<k; i++)
    {
        scanf ("%d",&n[i]);
    }
    mass();
    for (int i=0; i<k; i++)
    {
        
        p=n[i];
        prost(p);
    }
    
    scanf("%d",&k);
}
void mass () //Функция вычисления простых чисел;
{
    int p=2, i2=2; 
    for (int i=2; i<=o; i++) //заполняем массив числами
    {
        t[i]=i;
    }
    
    
    while (p<o)  // Алгоритм Эратосфена
    {
        while (t[p]!=-1)
        {
            while ( (i2 * p) <= o)
            {
                t[i2*p]=-1; 
                i2++;
            }
            i2=2;
            p++;
        }
        p++;
    }
}
void prost (int p)
{
    int j=2;
    while (p)
    {
        if (t[j]!=-1)
        {
            p--;
        }
        j++;
    }
    printf ("%d\n",t[j-1]);
}
Вопрос: Как можно оптимизировать код для более быстрой работы?
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
12.12.2010, 03:50     Простые числа.
Посмотрите здесь:

Найти простые числа с суммой цифр меньше заданного числа - C++
нужно написать прогу, можно использовать только циклы. Если можно, с объяснениями. Условие: Найти n первых простых чисел, сумма цифр у...

Найти сверхпростые числа: простые числа, номера которых являются простыми числами. - C++
Привет родные форумчане! Пожалуйста помогите решить буду особенно благодарен если напишите код с комментариями что как работает, заранее...

Вывести все простые числа до заданного числа - C++
Нужно вывести все простые числа до заданного числа N. С помощью процедуры и без массивов.

простые числа - C++
дана задача: вывести простые числа в диапазоне от 0 до 100000

Простые числа - C++
Помогите решить задачу! бьюсь над ней несколько часов...:wall: Найти разность квадрата суммы и суммы квадратов всех простых чисел от 1...

Простые числа - C++
У меня 2 задачи. Объясните, пожалуйста, просто алгоритмы. 1) Найти n-ное простое число (например n=10^5) 2) Разложение составного числа...

Простые числа - C++
Помогите сделать так, чтобы в этой программе не считал все четные числа(2,4,6,8...), а просто пропускал их. #define SIZE 32767 //вводит...

Простые числа - C++
Проверить является ли введеное число простым или нет. Запрещено создавать темы с бессмысленными названиями вроде &quot;Помогите!&quot;, &quot;Вопрос&quot; и...

Простые числа - C++
Доброго дня. Данный код проверяет ,является ли число простым. Есть ли альтернативный алгоритм проверки ,более &quot;компактный&quot; ? #include...

простые числа - C++
Дана последовательность натуральных чисел длины n. Вычислить сумму тех из них, которые – простые числа.

Простые числа - C++
Привет всем! Ребята, помогите написать программу: 1). Найти все простые числа, меньше заданного &quot;n&quot; 2). Найти все простые делители...

Простые числа - C++
Народ, выручайте снова! Почему когда в матрице появляется 5 или 7 их прога записывает много раз? Задание вот такое Дана матpица A....


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
valeriikozlov
Эксперт C++
4669 / 2495 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
12.12.2010, 07:45     Простые числа. #2
Вопрос: Как можно оптимизировать код для более быстрой работы?
Во первых, по моим подсчетам у Вас в массиве t[] находится всего 1756 первых простых чисел.
Во вторых, для каждого очередного числа в новой строке Вам приходится для нахождения простого числа искать его с самого начала массива t[].
Вся оптимизация должна будет заключаться в том что бы сделать изначально массив в котором только простые числа и найти тогда это число будет очень просто и самое главное быстро.
Алгоритм нахождения таким образом недавно обсуждался здесь:
Всё просто
Самый первый код volovzi реализует этот алгоритм.
Yandex
Объявления
12.12.2010, 07:45     Простые числа.
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru