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

Эффективный алгоритм поиска простых чисел на С++ - C++

Войти
Регистрация
Восстановить пароль
Другие темы раздела
C++ Вывести значение логического выражения, заданного в виде строки S. Выражение определяется следующим образом («T» — True, «F» — False): <выражение> : http://www.cyberforum.ru/cpp-beginners/thread853990.html
помогите пожалуйста решить задачку на рекурсию Вывести значение логического выражения, заданного в виде строки S. Выражение определяется следующим образом («T» — True, «F» — False): <выражение> ::= T | F | And(<выражение> , <выражение>) | Or(<в ыражение> ,<выражение>)
C++ Дан символ 'C' (прописная латинская буква) и текстовый файл. Создать строковый файл, содержащий все слова из исходного файла Дан символ 'C' (прописная латинская буква) и текстовый файл. Создать строковый файл, содержащий все слова из исходного файла, начинающиеся этой буквой (как прописной, так и строчной). Знаки препинания, расположенные в начале и в конце слов, не учитывать. Если исходный файл не содержит подходящих слов, оставить результирующий файл пустым. Нужно СРОЧНО!!! Добавлено через 10 минут хотя бы... http://www.cyberforum.ru/cpp-beginners/thread853979.html
C++ Условие в условии
Здравствуйте всем. Периодически нужно менять условия и поэтому одно из двух условий делал неактивным помещая в /*----*/ if( условие 1 /*условие 2*/ ){очень много строк}
C++ Перегруженный оператор вывода
Пытаюсь написать шаблон для работы с бинарными деревьями поиска. Возникла проблема - с ходу не соображу что к чему. при попытке распечатать дерево выдает ошибку " error LNK2019: ссылка на неразрешенный внешний символ "class std::basic_ostream<char,struct std::char_traits<char> > & __cdecl operator<<(class std::basic_ostream<char,struct std::char_traits<char> > &,class Tree<double>)"...
C++ Программа для нахождения в каждой строке матрицы G(n, m) максимальный и минимальный элементы http://www.cyberforum.ru/cpp-beginners/thread853948.html
Напишите программу для нахождения в каждой строке матрицы G(n, m) максимальный и минимальный элементы и помещения их на место первого и последнего элемента строки соответственно. Вывести на экран исходную и полученную матрицы в общепринятом виде.
C++ Составить программу, которая по номеру детали выводит на экран её название. Вот задание. Имеется пронумерованный список деталей: 1) шуруп, 2) гайка, 3) винт, 4) гвоздь,5)болт. Составить программу, которая по номеру детали выводит на экран её название. Вот какой код я смог придумать. Но почему-то он не хочет работать. Где ошибка ? #include<iostream.h> #include<conio.h> void main () { int a; clrscr(); cout <<"a="; cin>>a; switch (a); { case1: cout<<"shyryp";... подробнее

Показать сообщение отдельно
-=ЮрА=-
Заблокирован
Автор FAQ
03.05.2013, 20:27     Эффективный алгоритм поиска простых чисел на С++
Цитата Сообщение от Ternsip Посмотреть сообщение
-=ЮрА=-, напишите код, я его проверю на контесторе, я сомневаюсь в справедливости сказанного. В вашем рассуждении вы делаете ужасную ошибку, вы думаете, что через разряды, не зависимо от числа, можно проверять его на делимость....
http://www.cyberforum.ru/cgi-bin/latex.cgi?\begin{matrix} <br />
a   &  b  \\  <br />
k   & 1EN \\  <br />
10*k & 1EN /(10*k)  = 1EN - 1\\  <br />
100*k & 1EN /(100*k) = 1EN - 2  \\ <br />
 .... & \\  <br />
k*E(N/2) & 1EN /[k*E(N/2)] = 1E(N/2)<br />
 \end{matrix}
Я уже приводил выкладки, проверить все делители можно до SQRT(N) - прошу не надо спорить там где это очевидно.
(Ещё раз если a*b = c и a < SQRT(c) то b > SQRT(c) а стало быть баланс а и b существует только у корня из числа, далее идёт повторение делителей).На счёт кода - вот пока неоптимизированный вариант (в данный момент усиленно думаю над нижней границей проверки, верней как сделать начало не с 11 а поднимать степень и у начала)
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
62
63
64
65
66
#include <cmath>
#include <iostream>
using namespace std;
 
bool isSimple(long long num);
double OPCount = 0;
 
int main()
{
    long long nCount  = 0;
    long long num     = 0;
    for(num = 2; num < 999984; num++)
    {
        if(isSimple(num))
        {
            nCount++;
            cout<<"\rNUM  : "<<num;
            cout<<" ITERS : "<<OPCount
                <<" COUNT : "<<nCount;
        }
    }
    cout<<"\nOTHER TESTS : "<<endl;
    if(isSimple(9999999900000001))
        cout<<"IS SIMPLE"<<endl;
    if(isSimple(2147483647))
        cout<<"IS SIMPLE"<<endl;
    if(isSimple(1244042141))
        cout<<"IS SIMPLE"<<endl;
    else
        cout<<"NOT SIMPLE"<<endl;
    system("pause");
    return 0;
}
 
bool isSimple(long long num)
{
    long long i     = 0;
    long long limit = 10;
    bool bSimple = true;
    if( num < 0 )
        num *= -1;
    OPCount += 1;
    for(i = 2; i <= 9 && bSimple; i++)
    {
        OPCount += 1;
        if( i != num )
            bSimple = num % i != 0;
    }
    if( bSimple )
    while(limit * limit < num)
    {
          limit   *= 10;
          OPCount += 1;
    }
    //3.2 чтобы перкрыть корень sqrt 10 максимум что можем получить
    limit = 32*limit;
    limit = limit / 10;
    OPCount += 2;
    for(i = 9 + 2; i <= limit && bSimple; i += 2)
    {
        if( i != num )
            bSimple = num % i != 0;
        OPCount += 1;
    } 
    return bSimple;
}
Без сомнения на 1Е6 чисел даже в утяжелённом (100% надёжном варианте), алгоритм лучше вашего Ternsip, зачем упорствовать?Надо думать как ускорить и уменьшить число операций, а не освистывать

Давайте ещё раз по полочкам
Цитата Сообщение от Ternsip Посмотреть сообщение
ля абсолютного теста я возьму несколько больших чисел (около 10 шт) и просумирую время выполнения вашего и моего алгоритма на них, в случае, если вы сможете написать код, который работает правильно
- я пока могу гаранитровать эффективность на числах думаю 10E7-8 (ну так и думаю я всего 2-й день). Также для адекватной оценки прошу в вашем коде в строчке pow проставить не +1 а плюс i в зависимости от показателя степени (я занижаю число операций в вашем алгоритме чуть ли не в 100 раз)...
Миниатюры
Эффективный алгоритм поиска простых чисел на С++  
 
Текущее время: 04:59. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru