Бұл не?
Сабақтың тақырыбы — «Жай сандар». Талдап көрейік. Конструктордың кішкентай кірпіштерден құрастыруға болатын бөлшектері бар, ал одан әрі бөлшектенбейтін кірпіштердің өзі де бар. Жай сандар — осындай кірпіштер: олардың дәл екі бөлгіші бар, бір және санның өзі. Мысалы, жеті тек бірге және жетіге бөлінеді, ал он екі кішірек сандардан құралады — ол құрама сан.
Бұл не үшін керек?
Орасан зор жай сандар бүкіл интернетті күзетеді: сатып алуларды, хат алмасу мен құпиясөздерді қорғайтын шифрлау алгоритмдері соларға құрылған, сондықтан үлкен санды көбейткіштерге жіктеу қиын болуы өте маңызды. Жай сандарды кездейсоқ сандар генераторларында, бағдарламалардың ішіндегі хеш-кестелердің құрылысында, тіпті механизмдердің тісті дөңгелектерін есептеуде де пайдаланады. Жасанды интеллект сандарды кез келген адамнан жылдам тексере алады, бірақ сенімді қорғаныс ойлап тауып, оның әлсіз жерін түсіне алатын — сандардың қалай құрылғанын білетін адамдар ғана. Киберқауіпсіздік пен криптографияның мұндай мамандарына сұраныс өте жоғары.
Бұл қалай жұмыс істейді?
Жүзге дейінгі барлық жай санды табу үшін електі пайдаланады: бірден басқа ең кіші сызылмаған санды аламыз — ол жай сан, және оған еселі сандардың бәрін сызып тастаймыз. Содан кейін келесі сызылмаған санды алып, қайталаймыз. Құрама сандар електе тұрып қалады, ал жай сандар өтіп кетеді. Бір — ерекше сан: оның бір ғана бөлгіші бар, сондықтан ол жай да емес, құрама да емес.
Аздап тарих
Електі мысырлық Александрияда өмір сүріп, оның әйгілі кітапханасын басқарған грек ғалымы Эратосфен ойлап тапқан. Ол басқа нәрсемен де атағы шықты: екі қаладағы көлеңкелердің ұзындығы бойынша бүкіл Жердің өлшемін едәуір дәл есептей алды. Ал одан да ертерек Евклид жай сандардың шексіз көп екенін дәлелдеген.
Практикада не істейміз?
Ал енді практикалық тапсырманы орындап көрейік. Алдыңда бірден жүзге дейінгі сандар кестесі тұр — бұл Эратосфен елегі, және онда жетпіс төрт құрама санның бәрін сызып тастау керек. Жай сан бола алатын ең кіші саннан баста, оны белгіле де, оған қандай сандар еселі екенін ойла, — оларды сызып тастауға болады. Содан кейін келесі сызылмаған санды тауып, қайтала. Байқа, осы кезде көп сандар сызылып қойған, — неліктен екенін және жұмысты қай сәтте аяқтауға болатынын ойлап көр. Бірдеңе түсініксіз болып қалса — ештеңе етпейді, менен кез келген нәрсені сұра, жауап беремін. Уайымдама.