Форум программистов
 

Восстановите пароль или Зарегистрируйтесь на форуме, о проблемах и с заказом рекламы пишите сюда - alarforum@yandex.ru, проверяйте папку спам!

Вернуться   Форум программистов > C/C++ программирование > Общие вопросы C/C++
Регистрация

Восстановить пароль
Повторная активизация e-mail

Купить рекламу на форуме - 42 тыс руб за месяц

Ответ
 
Опции темы Поиск в этой теме
Старый 17.03.2018, 00:12   #1
rekimchuk
Пользователь
 
Регистрация: 12.03.2018
Сообщений: 11
По умолчанию Нужно найти 2 последних простых числа, от 5 до n. 5<=n<10^9. За 0.1сек.

У меня тут проблемка. Весь код написан, а я должен написать только функцию которая будет находить 2 последних простых числа, от 5 до n.
Пробовал с помощью Решето Эратосфена, и сделать array[10^9], был слишком большой, мне пишет что максимум можно сделать 10^8 . Подумал что пусть хотяб так, тоже норм должно быть. хотя 50% будет решено. Но 9/10 ответов не верны и 1/10 просто превышен лимит времени.
Допустим дано n=28. тогда a=23 . b=19.
Код:
void sub(int n, int &x,int &y)
{
    int a,b;
    unsigned long long tab[100000000]={1};
    for(int i = n + 1 ; i <= 100000000 ; i++)
    {
        tab[i]=0;
    }
    for(unsigned long long i = 5 ; i < n; i++)
    {
        for(unsigned long long j = i * i ; j <= n ; j += i)
        {
            if(j>n)break;
            tab[j]=0;
        }
    }
    for(int i = 100000000 ; i >= 5 ; i--)
    {
        if(tab[i]==1)
        {
            a=i;
            if(a!=0)b=i;
        }
        if(a != 0 && b != 0)break;
    }
}
Где у меня тут ошибки? подскажите пожалуйста.
rekimchuk вне форума Ответить с цитированием
Старый 17.03.2018, 00:26   #2
waleri
Старожил
 
Регистрация: 13.07.2012
Сообщений: 6,493
По умолчанию

Для хранения 0 и 1 достаточно 1 бита, у вас же в массиве tab 0/1 хранятся в 64 битах! Одними только битовыми операциями, прочих равных, емкость массива увеличится в 64 раза!
waleri вне форума Ответить с цитированием
Старый 17.03.2018, 00:39   #3
rekimchuk
Пользователь
 
Регистрация: 12.03.2018
Сообщений: 11
По умолчанию

В кодблоке ошибок вроде бы нету. можно создавать bool [10^9]. а вот на сайте с тестом даёт ошибку с памятью. я превысил лимит памяти типо. caught fatal signal 11
----------------
немного улучшил(но это не точно) код, и всё равно как то рукожопно.
Код:
void sub(int n, int &x,int &y)
{
    //int a,b;
    bool tab[100000000]={1};
    for(int i = n + 1 ; i <= 100000000 ; i++)
    {
        tab[i]=0;
    }
    for(long long i = 5 ; i < n; i++)
    {
        for(long long j = i * i ; j <= n ; j += i)
        {
            if(j>n)break;
            tab[j]=0;
        }
    }
    for(int i = 100000000 ; i >= 5 ; i--)
    {
        if(tab[i]==1)
        {
            x=i;
            if(x!=0)
            {
                y=i;
                break;
            }
        }
    }
}
rekimchuk вне форума Ответить с цитированием
Старый 17.03.2018, 06:39   #4
Black Fregat
Программист
Участник клуба
 
Аватар для Black Fregat
 
Регистрация: 23.06.2009
Сообщений: 1,772
По умолчанию

Я думаю, что для поиска двух простых чисел решето неэффективно.
Нужно идти назад прямыми проверками, причем только по числам вида 6n-1, 6n+1
И в лоб проверять делимость на нечётные числа от 5 до sqrt(n)
В сумме должно выйти быстрее, особенно для больших n
А уж по памяти точно выигрыш будет

Последний раз редактировалось Black Fregat; 17.03.2018 в 06:43.
Black Fregat вне форума Ответить с цитированием
Старый 17.03.2018, 09:06   #5
rekimchuk
Пользователь
 
Регистрация: 12.03.2018
Сообщений: 11
По умолчанию

Цитата:
Сообщение от Black Fregat Посмотреть сообщение
И в лоб проверять делимость на нечётные числа от 5 до sqrt(n)
я видел как другие делали так. с помощью sqrt. но никак не понимаю как с помощью корня найти 2 последних простых чисел.
rekimchuk вне форума Ответить с цитированием
Старый 17.03.2018, 10:20   #6
Аватар
Старожил
 
Аватар для Аватар
 
Регистрация: 17.11.2010
Сообщений: 19,042
По умолчанию

Убывающий цикл от 999999999
Вложенный возрастающий цикл до целой части корня переменной первого цикла с проверкой делимости. К 6n-1, 6n+1 можно не привязываться, и так быстро найдет для 10^9
Нашел 2 числа - выход из первого цикла
Если бы архитекторы строили здания так, как программисты пишут программы, то первый залетевший дятел разрушил бы цивилизацию
Аватар вне форума Ответить с цитированием
Старый 17.03.2018, 12:39   #7
rekimchuk
Пользователь
 
Регистрация: 12.03.2018
Сообщений: 11
По умолчанию

Цитата:
Сообщение от Аватар Посмотреть сообщение
Убывающий цикл от 999999999
Вложенный возрастающий цикл до целой части корня переменной первого цикла с проверкой делимости. К 6n-1, 6n+1 можно не привязываться, и так быстро найдет для 10^9
Нашел 2 числа - выход из первого цикла
Код:
void sub(int n, int &x,int &y)
{
    //int a,b;
    bool tab[999999999]={1};
    for(int i = n + 1 ; i <= 999999999 ; i++)
    {
        tab[i]=0;
    }
    for(long long i = 5 ; i < n; i++)
    {
        for(long long j = i * i ; j <= n ; j += i)
        {
            if(j>n)break;
            tab[j]=0;
        }
    }
    for(int i = 999999999 ; i >= sqrt(n) ; i--)
    {
        if(tab[i]==1)
        {
            x=i;
            if(x!=0)
            {
                y=i;
                break;
            }
        }
    }
}
Уже пробовал, не работает норм, то есть ответ не правильный. из за корня пишет error .
Код:
maxprime.cpp: In function 'void sub(int, int&, int&)':
maxprime.cpp:21:40: error: 'sqrt' was not declared in this scope
     for(int i = 999999999 ; i >= sqrt(n) ; i--)

Последний раз редактировалось rekimchuk; 17.03.2018 в 12:54.
rekimchuk вне форума Ответить с цитированием
Старый 17.03.2018, 12:52   #8
Аватар
Старожил
 
Аватар для Аватар
 
Регистрация: 17.11.2010
Сообщений: 19,042
По умолчанию

А зачем там массив здоровенный? Два же только найти нужно. И в остальном чушь полная. А с паскаля переведешь на плюсы? Пробуй
Код:
var i,j,Count: Integer;
    b: Boolean;
    a: array[0..1] of Integer;
...
  Count:=0;
  for i:=999999999 downto 1 do begin
    b:=True;
    for j:=2 to Trunc(Sqrt(i)) do if i mod j = 0 then begin b:=False; Break; end;
    if b then begin a[Count]:=i; Inc(Count); if Count = 2 then Break; end;
  end;
999999937
999999929
Если бы архитекторы строили здания так, как программисты пишут программы, то первый залетевший дятел разрушил бы цивилизацию
Аватар вне форума Ответить с цитированием
Старый 17.03.2018, 13:04   #9
rekimchuk
Пользователь
 
Регистрация: 12.03.2018
Сообщений: 11
По умолчанию

Спасибо за помощь, теперь надо перевести всё это, а это уже легче(надо лишь человека найти который шарит в паскаль) , я конечно понимаю немножко код. но есть некоторые вещи которые я в паскале не знаю )
rekimchuk вне форума Ответить с цитированием
Старый 18.03.2018, 17:48   #10
rekimchuk
Пользователь
 
Регистрация: 12.03.2018
Сообщений: 11
По умолчанию

Цитата:
Сообщение от Аватар Посмотреть сообщение
Код:
 Inc(Count);
что значит inc()? просто попытался сам перевести на с++. всё понял, кроме этого
rekimchuk вне форума Ответить с цитированием
Ответ


Купить рекламу на форуме - 42 тыс руб за месяц

Опции темы Поиск в этой теме
Поиск в этой теме:

Расширенный поиск


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
С++ Найти сумму всех простых чисел, не превосходящих заданного числа n Defx Помощь студентам 1 23.03.2017 12:50
Для каждого числа последовательности найти сумму его простых делителей Aibolat C++ Builder 0 04.10.2016 10:02
Нужно найти сумму всех простых делителей введённого числа AnnaMV Общие вопросы C/C++ 1 10.08.2016 08:24
програма которая виводит все простие числа от 1 до 1000000 до 1сек PAWLO1993 Паскаль, Turbo Pascal, PascalABC.NET 7 12.06.2008 01:15