Форум программистов
 
Контакты: о проблемах с регистрацией, почтой и по другим вопросам пишите сюда - alarforum@yandex.ru, проверяйте папку спам! Обязательно пройдите активизацию e-mail.

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

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

Ответ
 
Опции темы
Старый 17.03.2018, 01:12   #1
rekimchuk
Пользователь
 
Регистрация: 12.03.2018
Сообщений: 11
Репутация: 10
По умолчанию Нужно найти 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, 01:26   #2
waleri
Профессионал
 
Регистрация: 13.07.2012
Адрес: Нижний Новгород
Сообщений: 5,532
Репутация: 1777
По умолчанию

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

В кодблоке ошибок вроде бы нету. можно создавать 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, 07:39   #4
Black Fregat
Программист
Профессионал
 
Аватар для Black Fregat
 
Регистрация: 23.06.2009
Сообщений: 1,062
Репутация: 754
По умолчанию

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

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

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

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

Цитата:
Сообщение от Аватар Посмотреть сообщение
Убывающий цикл от 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 в 13:54.
rekimchuk вне форума   Ответить с цитированием
Старый 17.03.2018, 13:52   #8
Аватар
Модератор
Заслуженный модератор
 
Аватар для Аватар
 
Регистрация: 17.11.2010
Адрес: Северодонецк.ua
Сообщений: 17,991
Репутация: 6304
По умолчанию

А зачем там массив здоровенный? Два же только найти нужно. И в остальном чушь полная. А с паскаля переведешь на плюсы? Пробуй
Код:

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, 14:04   #9
rekimchuk
Пользователь
 
Регистрация: 12.03.2018
Сообщений: 11
Репутация: 10
По умолчанию

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

Цитата:
Сообщение от Аватар Посмотреть сообщение
Код:

 Inc(Count);

что значит inc()? просто попытался сам перевести на с++. всё понял, кроме этого
rekimchuk вне форума   Ответить с цитированием
Ответ

Опции темы

Ваши права в разделе
Вы не можете создавать новые темы
Вы не можете отвечать в темах
Вы не можете прикреплять вложения
Вы не можете редактировать свои сообщения

BB коды Вкл.
Смайлы Вкл.
[IMG] код Вкл.
HTML код Выкл.

Быстрый переход

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


10:42.


Powered by vBulletin® Version 3.8.8 Beta 2
Copyright ©2000 - 2018, Jelsoft Enterprises Ltd.

RusProfile.ru


Справочник российских юридических лиц и организаций.
Проекты отопления, пеллетные котлы, бойлеры, радиаторы
интернет магазин respective.ru