Есеп: Жай сандарды шығару

Есептер
Берілгені:
10 млн-ға дейінгі барлық жай сандарды экранға шыгарыңыз.

Жай сан — өзіне және 1-ге ғана қалдықсыз бөлінетін сан.

(Даулет)

50 пікір

avatar
Әлі ешкім пікір жазбаған ба?)
avatar
Сені күтіп отырған болар:)
avatar

int i = 1; 
while(i<10000000){
    int m = 0, s = 0;
    for(int j = 1; j<=i; j++){
        if(i%j == 0){
            m++;
        }
    }
    if(m = 2){
        cout<<"жәй сан "<<i;
    }
    i++;
}

Осылай ма?
avatar
Жауабы дұрыс шығып тұр ма? Негізі, әлде де оптимизировать етсе болады. Мысалға, ішкі циклда міндетті i-ге дейін тексеру шарт емес.
avatar
тексермедім))… жәй жаза салған түрім ғой… оптимизация… типа if(m>2) break;
avatar
ия, ол да бар екен ғой
avatar
(m == 2) емес (m <= 2) деп тексеру керек шығар, әйтпесе 1-ді қарастырмай кетеді
avatar
аа жоқ, 1 жай санға жатпайды екен ғой))) кешірім сұрайм))
avatar
Не деген уят мынау :(
avatar
дұрыс емес пе?)
avatar
Серверди кулаткын келсе, осындай циклдер жиберген жаксы гой =)))
avatar
С#-та жай сандарды кездейсоқ генерациялайтын арнайы класс бар ма? Болмаса жасап көрейік?! Маған сабаққа қажет болып тұр)
avatar
Генерация случайных чисел уже бар. Случайное число генерить етип {2,N} аралыгында, ен улкен жай санды таба коюга болады.
avatar
табылған ақыл) Рахмет
avatar
int N = Convert.ToInt32(Console.ReadLine());
            for (int i = 3; i <= N; i += 2)
            {
                int k = 0;
                for (int j = 3; j < i / 2; j+=2)
                {
                    if (i % j == 0)
                    {
                        k++;
                    }
                }
                if (k == 0)
                {
                    Console.Write(i + " ");
                }
            }
avatar
Дауреннин алгоритмимен почти бирдей жумыс истеп тур гой :)))
егер k>0 break; десениз, онда намного жылдам жасайды
avatar
Сонда ">" әрқашан "==" жылдам жасайды ма?

Менің алгоритмымда тек қана тақ сандарды, және екінші циклда i-дың жартысына дейін ғана тексереді.
avatar
ааа түсіндім түсіндім
avatar
int N = Convert.ToInt32(Console.ReadLine());
            for (int i = 3; i <= N; i += 2)
            {
                int k = 1;
                for (int j = 3; j < i / 2; j+=2)
                {
                    if (i % j == 0)
                    {
                        k = 0; break;
                    }
                    else
                    {
                        k++;
                    }
                }
                if (k > 0)
                {
                    Console.Write(i + " ");
                }   
            }
avatar
Мынау әдемірек секілді
int N = Convert.ToInt32(Console.ReadLine());
            for (int i = 3; i <= N; i += 2)
            {
                int k = 0;
                for (int j = 3; j < i / 2; j+=2)
                {
                    if (i % j == 0)
                    {
                        k++; break;
                    }
                    else
                    {
                        k=0;
                    }
                }
                if (k == 0)
                {
                    Console.Write(i + " ");
                }   
            }
avatar
машалла, сиз бираз оптимизировать еттиниз :), бирак али де коп оптимизировать етуге болады.
avatar
О о, ары қарай тағы қалай оптимизировать етуге болады? 14 мин болды әрі есептеп жатыр 10млн-ға дейін.
avatar
Решето Эратосфена, окыныз
avatar
типа n%(sqrt(n))!=0;
avatar
не то что, дурыстап окыныз :))
avatar
есе сандарды сызып отыратын… но онын алгоритмін калай жазса болад екен?
avatar
10 миллионга дейін…
avatar
Ия солай, скоро размещать етемин программный кодты, казирше оздериниз тырысып караныздар!
avatar
Келеси есеп, агаш берилген, агаштын бир буынынан баска кез келген буынына баратын жолдар санын табыныз
avatar
Дәке, есепті бөлек постқа, берілген толығырақ жазсаңыз. Анау-мынауын өзім түзеп қоям ғо)
avatar
Сонымен қатар, егер қолданушы жазба қосқан сайын оның рейтингі көтерілетінін айта кетейін. Және лайк басылған жазба, пікірлердің авторының рейтингі өседі.
avatar
Ия артынан толыктырып жазамын иншалла, пример келтирип
avatar
Бұл теория принятие решениеге арналған есеп пе?)
avatar
Агаш туралы ма? Жок ол графтарга жатады вроде :) Агаш деген графтын бир тури гой, менин тусинуим бойынша :)
avatar
Бізде Дәке, Бәкелер көбейіп жатыр))
avatar
10 млн — га дейинги барлык жай сандарды 4 секундта шыгарады :)

int n=10000000;
Date start = new Date();
boolean a[] = new boolean[n];
for (int i=0;i<n;i++)
{
a[i]=true;
}
int i=2;
while (i*i<n)
{
if (a[i])
{
int j=i*i;
while (j<n)
{
a[j] = false;
j = j+i;
}
}
i++;
}
for (int k=2;k<a.length;k++)
{
if (a[k])
System.out.println(k);
}
System.out.println(«start:»+start + ", end:"+new Date());
avatar
4 сек өте керемет!
avatar
Керемет! Сызып тастауды true false арқылы жазу мүлдем ойға келмепті…
avatar
Бул менин ойым емес, википедия гой :)). Мен дал солай, бирак сандарды нольге айналдырып отыргым келген и кай жерде ноль емес, сол жай сан болгандай. Бирак булен все так аз колем алады, более оптимальный вариант память бойынша, ал скорость бойынша бирдей болу керек
avatar
4 секундта расымен осынша көп операцияны орындап шығады ма?)
avatar
ия, тексерип карадым :)
avatar
C#-та осы кодты жазып едім, 34 секунд болды :)
avatar
ондай улкен разница болу мумкин емес, просто экранга шыгару шамалы жай орындалса керек. 2 тилде де результатты просто баска массивке присвойть етип караныз, ЭКРАНГА ШЫГАРМАЙ. Примерно бирдей болу керек
avatar
олай моментально жасап берди :)
бірінші мен ақырғысын ғана шығардым
avatar
dotnetchik, жоғарыдағы есебіңізде екінші циклды неге осылай жаздыңыз? for (int j = 3; j < i / 2; j+=2)
avatar
Ия, 2-нің жай сан екенін ұмытып кетіппін. i/2 екі емес, sqrt(i) болса дұрысырақ. Сондай қағида бар.
avatar
j+=2 жұп сандарды аттап кетіп жатырмын
avatar
Сондай-ақ, сіздің есебіңізде массив 3-тен басталып тұр, 2 де жай санға жатады емес пе, қателеспесем,
avatar
енді түсіндім :), бірақ сонда да екінші циклда неге i-дің жартысына дейін ғана тексеретін етіп алдыңыз?
avatar
Ботик) ол жерлерде қателіктер бар ғой… дұрысы мұнда тұр
Тек қана тіркелген және авторизациядан өткен қолданушылар пікір қалдыра алады.