X არის მარტივი რიცხვი. როგორ მოვძებნოთ მარტივი რიცხვები
პრობლემა 2.30
მოცემულია ერთგანზომილებიანი A მასივი, რომელიც შედგება ბუნებრივი რიცხვებისგან. აჩვენეთ მასივის მარტივი რიცხვების რაოდენობა.
პირველ რიგში, ნება მომეცით შეგახსენოთ, რა არის ეს მარტივი რიცხვები.
ახლა გადავიდეთ დავალებაზე. არსებითად, ჩვენ გვჭირდება პროგრამა, რომელიც განსაზღვრავს მარტივ რიცხვებს. და ელემენტების დალაგება და მათი მნიშვნელობების შემოწმება ტექნოლოგიის საკითხია. ამავდროულად, ჩვენ შეგვიძლია არა მხოლოდ დათვლა, არამედ მასივის მარტივი რიცხვების ჩვენებაც.
როგორ განვსაზღვროთ მარტივი რიცხვი პასკალში
მე შემოგთავაზებთ გადაწყვეტის ალგორითმს დეტალური ანალიზით პასკალში. გამოსავალი შეგიძლიათ ნახოთ სამაგალითო პროგრამაში C++-ში.
მნიშვნელოვანია!
ეს არის ის, სადაც ბევრი ადამიანი შეიძლება შეცდეს. განმარტება ამბობს, რომ პირველ რიცხვს აქვს გლუვიორი განსხვავებულიგამყოფი მაშასადამე, რიცხვი 1 არ არის მარტივი (ასევე არ არის მარტივი, რადგან ნული შეიძლება გაიყოს ნებისმიერ რიცხვზე).
ჩვენ შევამოწმებთ არის თუ არა რიცხვი მარტივი გამოყენებით , რომელსაც ჩვენ თავად შევქმნით. ეს ფუნქცია დააბრუნებს TRUE-ს, თუ რიცხვი მარტივია.
ფუნქციაში ჯერ შევამოწმებთ არის თუ არა რიცხვი ორზე ნაკლები. თუ ასეა, მაშინ ის აღარ არის მარტივი რიცხვი. თუ რიცხვი არის 2 ან 3, მაშინ ის ცალსახად მარტივია და ზოგიერთი რამის გაკეთება შესაძლებელია დამატებითი შემოწმებებიარ არის საჭირო.
მაგრამ თუ რიცხვი N სამზე მეტია, მაშინ ამ შემთხვევაში ჩვენ ყველა შესაძლო გამყოფის ციკლს გავატარებთ, დაწყებული 2-დან (N-1-მდე). თუ რიცხვი N იყოფა რომელიმე გამყოფზე ნაშთის გარეშე, მაშინ ის ასევე არ არის მარტივი რიცხვი. ამ შემთხვევაში ჩვენ ვწყვეტთ ციკლს (რადგან აზრი არ აქვს შემდგომ შემოწმებას) და ფუნქცია აბრუნებს FALSE-ს.
არ აქვს აზრი იმის შემოწმებას, იყო თუ არა რიცხვი თავისთავად (ამიტომ მარყუჟი გრძელდება მხოლოდ N-1-მდე).
თავად ფუნქციას აქ არ წარმოვადგენ - შეხედეთ მას სანიმუშო პროგრამებში.
2.30 ამოცანის ამოხსნა პასკალში mytask; //**************************************************** ************* //მუდმივები //**************************** ********* ************************************ COUNT = 100; //ელემენტების რაოდენობა მასივში //**************************************** ********** ********************* // ფუნქციები და პროცედურები //************ ************************************************** ** //******** ************************************* * ******** // ამოწმებს რიცხვი მარტივია თუ არა // INPUT: N - ნომერი // OUTPUT: TRUE - ნომერი N არის მარტივი, FALSE - არა მარტივი //************ ******************************************** **** IsPrimeNumber(N: WORD) : ; var i: ; დაწყება := TRUE;
N 0..3-დან: დაწყება N გასვლა;დასასრული;
;
დასასრული; დასასრული;
ძალიან ხშირად, სკოლის მოსწავლეებმა არ იციან როგორ უპასუხონ ერთი შეხედვით მათემატიკის ერთ-ერთ ყველაზე მარტივ კითხვას იმის შესახებ, თუ რა არის მარტივი რიცხვი. ისინი ხშირად ურევენ მარტივ რიცხვებს ბუნებრივ რიცხვებთან (ანუ რიცხვებს, რომლებსაც ადამიანები იყენებენ საგნების დათვლისას, ზოგიერთ წყაროში კი ისინი იწყება ნულით, ზოგში კი ერთით). მაგრამ ეს არის სრულიად ორი განსხვავებული კონცეფცია. მარტივი რიცხვები არის ნატურალური რიცხვები, ანუ მთელი და დადებითი რიცხვები, რომლებიც ერთზე მეტია და რომლებსაც აქვთ მხოლოდ 2 ბუნებრივი გამყოფი. უფრო მეტიც, ამ გამყოფებიდან ერთი არის მოცემული რიცხვი, ხოლო მეორე არის ერთი. მაგალითად, სამი არის მარტივი რიცხვი, რადგან ის ნარჩენის გარეშე არ შეიძლება გაიყოს სხვა რიცხვზე, გარდა მისი და ერთისა.
კომპოზიტური რიცხვები
მარტივი რიცხვების საპირისპირო არის შედგენილი რიცხვები. ისინი ასევე ბუნებრივია, ასევე ერთზე მეტი, მაგრამ აქვთ არა ორი, არამედ უფრო დიდი რაოდენობის გამყოფები. ასე, მაგალითად, რიცხვები 4, 6, 8, 9 და ა.შ. არის ბუნებრივი, შედგენილი, მაგრამ არა მარტივი რიცხვები. როგორც ხედავთ, ეს ძირითადად ლუწი რიცხვებია, მაგრამ არა ყველა. მაგრამ "ორი" არის ლუწი რიცხვი და "პირველი რიცხვი" მარტივი რიცხვების სერიაში.
ქვემიმდევრობა
მარტივი რიცხვების სერიის ასაგებად, აუცილებელია ყველა ნატურალური რიცხვიდან არჩევა, მათი განმარტების გათვალისწინებით, ანუ თქვენ უნდა იმოქმედოთ წინააღმდეგობით. აუცილებელია თითოეული დადებითი ნატურალური რიცხვის შესწავლა იმის გასარკვევად, აქვს თუ არა მას ორზე მეტი გამყოფი. შევეცადოთ ავაშენოთ რიგი (მიმდევრობა), რომელიც შედგება მარტივი რიცხვებისგან. სია იწყება ორით, რასაც მოჰყვება სამი, რადგან ის მხოლოდ თავისთავად და ერთით იყოფა. განვიხილოთ ნომერი ოთხი. ოთხი და ერთის გარდა სხვა გამყოფები აქვს? დიახ, ეს რიცხვია 2. ასე რომ, ოთხი არ არის მარტივი რიცხვი. ხუთი ასევე მარტივია (ის არ იყოფა სხვა რიცხვზე, გარდა 1-ისა და 5-ისა), მაგრამ ექვსი იყოფა. და საერთოდ, თუ ყველა ლუწი რიცხვს მიჰყვებით, შეამჩნევთ, რომ „ორის“ გარდა, არცერთი მათგანი არ არის მარტივი. აქედან ვასკვნით, რომ ლუწი რიცხვები, გარდა ორისა, მარტივი არ არის. კიდევ ერთი აღმოჩენა: ყველა რიცხვი, რომელიც იყოფა სამზე, გარდა თავად სამისა, ლუწი თუ კენტი, ასევე არ არის მარტივი (6, 9, 12, 15, 18, 21, 24, 27 და ა.შ.). იგივე ეხება რიცხვებს, რომლებიც იყოფა ხუთზე და შვიდზე. მთელი მათი სიმრავლე ასევე არ არის მარტივი. შევაჯამოთ. ასე რომ, მარტივი ერთნიშნა რიცხვები მოიცავს ყველა კენტ რიცხვს გარდა ერთისა და ცხრასა და ლუწი „ორი“ არის ლუწი რიცხვები. თავად ათეულები (10, 20,... 40 და ა.შ.) მარტივი არ არის. ორნიშნა, სამნიშნა და ა.შ. მარტივი რიცხვების დადგენა შესაძლებელია ზემოაღნიშნული პრინციპების საფუძველზე: თუ მათ არ აქვთ გამყოფები საკუთარი თავისა და ერთის გარდა.
თეორიები მარტივი რიცხვების თვისებების შესახებ
არსებობს მეცნიერება, რომელიც სწავლობს მთელი რიცხვების თვისებებს, მათ შორის მარტივ რიცხვებს. ეს არის მათემატიკის ფილიალი, რომელსაც უმაღლესი ეწოდება. მთელი რიცხვების თვისებების გარდა, იგი ასევე ეხება ალგებრულ და ტრანსცენდენტურ რიცხვებს, ასევე სხვადასხვა წარმოშობის ფუნქციებს, რომლებიც დაკავშირებულია ამ რიცხვების არითმეტიკასთან. ამ კვლევებში, გარდა ელემენტარული და ალგებრული მეთოდებისა, გამოიყენება ანალიტიკური და გეომეტრიულიც. კერძოდ, "რიცხვთა თეორია" ეხება მარტივი რიცხვების შესწავლას.
მარტივი რიცხვები ნატურალური რიცხვების „სამშენებლო ბლოკებია“.
არითმეტიკაში არსებობს თეორემა, რომელსაც ფუნდამენტური თეორემა ეწოდება. მისი მიხედვით, ნებისმიერი ნატურალური რიცხვი, გარდა ერთისა, შეიძლება წარმოდგენილი იყოს ნამრავლად, რომლის ფაქტორები არის მარტივი რიცხვები, ხოლო ფაქტორების რიგი უნიკალურია, რაც ნიშნავს, რომ წარმოდგენის მეთოდი უნიკალურია. მას უწოდებენ ნატურალური რიცხვის მარტივ ფაქტორებად გადაქცევას. ამ პროცესს კიდევ ერთი სახელი აქვს - რიცხვების ფაქტორიზაცია. ამის საფუძველზე, პირველ რიცხვებს შეიძლება ეწოდოს " სამშენებლო მასალა”, ”ბლოკები” ნატურალური რიცხვების ასაგებად.
მოძებნეთ მარტივი რიცხვები. სიმარტივის ტესტები
მრავალი მეცნიერი სხვადასხვა დროს ცდილობდა ეპოვა გარკვეული პრინციპები (სისტემები) მარტივი რიცხვების სიის საპოვნელად. მეცნიერებამ იცის სისტემების შესახებ, რომლებსაც უწოდებენ ატკინის საცერს, სუნდართამის საცერს და ერატოსთენეს. თუმცა, ისინი არ იძლევიან რაიმე მნიშვნელოვან შედეგს და მარტივი რიცხვების საპოვნელად ვიყენებთ მარტივი შემოწმება. მათემატიკოსებმა ასევე შექმნეს ალგორითმები. მათ ჩვეულებრივ უწოდებენ პირველობის ტესტებს. მაგალითად, არსებობს რაბინისა და მილერის მიერ შემუშავებული ტესტი. მას იყენებენ კრიპტოგრაფები. ასევე არსებობს Kayal-Agrawal-Sasquena ტესტი. თუმცა, მიუხედავად საკმარისი სიზუსტისა, ძალიან რთულია გამოთვლა, რაც ამცირებს მის პრაქტიკულ მნიშვნელობას.
აქვს თუ არა მარტივი რიცხვების სიმრავლეს ზღვარი?
ძველი ბერძენი მეცნიერი ევკლიდე თავის წიგნში „ელემენტები“ წერდა, რომ მარტივი რიცხვების სიმრავლე არის უსასრულობა. მან ასე თქვა: „მოდით, ერთი წუთით წარმოვიდგინოთ, რომ მარტივ რიცხვებს აქვთ საზღვარი. შემდეგ გავამრავლოთ ისინი ერთმანეთში და ერთი დავამატოთ ნამრავლს. ამ მარტივი მოქმედებების შედეგად მიღებული რიცხვი არ შეიძლება დაიყოს მარტივი რიცხვების არცერთ სერიზე, რადგან დარჩენილი იქნება ყოველთვის ერთი. ეს ნიშნავს, რომ არის სხვა რიცხვი, რომელიც ჯერ არ არის შეტანილი მარტივი რიცხვების სიაში. მაშასადამე, ჩვენი ვარაუდი არ შეესაბამება სიმართლეს და ამ კომპლექტს არ შეიძლება ჰქონდეს ლიმიტი. ევკლიდეს მტკიცებულების გარდა, არსებობს უფრო თანამედროვე ფორმულა, რომელიც მოცემულია მეთვრამეტე საუკუნის შვეიცარიელი მათემატიკოსის ლეონჰარდ ეილერის მიერ. მისი მიხედვით, პირველი n რიცხვის ჯამის საპასუხო ჯამი შეუზღუდავად იზრდება n რიცხვის მატებასთან ერთად. და აი, თეორემის ფორმულა მარტივი რიცხვების განაწილებასთან დაკავშირებით: (n) იზრდება როგორც n/ln (n).
რა არის ყველაზე დიდი მარტივი რიცხვი?
იგივე ლეონარდ ეილერმა შეძლო თავისი დროის უდიდესი მარტივი რიცხვის პოვნა. ეს არის 2 31 - 1 = 2147483647. თუმცა, 2013 წლისთვის გამოითვალა კიდევ ერთი ყველაზე ზუსტი უდიდესი რიცხვების სიაში - 2 57885161 - 1. მას მერსენის რიცხვი ჰქვია. იგი შეიცავს დაახლოებით 17 მილიონ ათობითი ციფრს. როგორც ხედავთ, მეთვრამეტე საუკუნის მეცნიერის მიერ ნაპოვნი რიცხვი ამაზე რამდენჯერმე მცირეა. ასეც უნდა ყოფილიყო, რადგან ეილერმა ეს გამოთვლა ხელით ჩაატარა, მაგრამ ჩვენს თანამედროვეს, ალბათ, დაეხმარა კომპიუტერი. უფრო მეტიც, ეს რიცხვი მიიღეს მათემატიკის ფაკულტეტზე, ერთ-ერთ ამერიკულ დეპარტამენტში. ამ მეცნიერის სახელობის ნომრები გადიან Luc-Lemaire-ის პირველობის ტესტს. თუმცა, მეცნიერებას არ სურს აქ გაჩერება. Electronic Frontier Foundation, რომელიც დაარსდა 1990 წელს ამერიკის შეერთებულ შტატებში (EFF), შესთავაზა ფულადი ჯილდო დიდი მარტივი რიცხვების პოვნისთვის. და თუ 2013 წლამდე პრიზი ენიჭებოდა იმ მეცნიერებს, რომლებიც იპოვნიდნენ მათ 1 და 10 მილიონი ათობითი რიცხვებიდან, დღეს ეს მაჩვენებელი 100 მილიონიდან 1 მილიარდამდეა. პრიზები 150-დან 250 ათას აშშ დოლარამდე მერყეობს.
სპეციალური მარტივი რიცხვების სახელები
იმ ციფრებს, რომლებიც აღმოაჩინეს გარკვეული მეცნიერების მიერ შექმნილი ალგორითმების წყალობით და გაიარეს სიმარტივის ტესტი, სპეციალური ეწოდება. აქ არის რამდენიმე მათგანი:
1. მერსენი.
4. კულენი.
6. მილსი და სხვ.
ზემოაღნიშნული მეცნიერების სახელობის ამ რიცხვების სიმარტივე დადგენილია შემდეგი ტესტების გამოყენებით:
1. ლუკ-ლემერი.
2. პეპინა.
3. რიზელი.
4. ბილჰარტი - ლემერი - სელფრიჯი და სხვები.
თანამედროვე მეცნიერება ამით არ ჩერდება და, ალბათ, უახლოეს მომავალში მსოფლიო შეიტყობს იმათ სახელებს, ვინც შეძლეს 250 000 დოლარის პრიზის მიღება უდიდესი მარტივი რიცხვის აღმოჩენით.
ილიას პასუხი სწორია, მაგრამ არც ისე დეტალური. მე-18 საუკუნეში, სხვათა შორის, ერთი ჯერ კიდევ პირველ რიცხვად ითვლებოდა. მაგალითად, ისეთი დიდი მათემატიკოსები, როგორებიც არიან ეილერი და გოლდბახი. გოლდბახი არის ათასწლეულის შვიდი პრობლემისგან ერთ-ერთის – გოლდბახის ჰიპოთეზის ავტორი. თავდაპირველ ფორმულირებაში ნათქვამია, რომ ყოველი ლუწი რიცხვი შეიძლება წარმოდგენილი იყოს ორი მარტივი რიცხვის ჯამად. უფრო მეტიც, თავდაპირველად 1 იყო გათვალისწინებული, როგორც მარტივი რიცხვი და ჩვენ ვხედავთ ამას: 2 = 1+1. ეს არის ყველაზე პატარა მაგალითი, რომელიც აკმაყოფილებს ჰიპოთეზის თავდაპირველ ფორმულირებას. მოგვიანებით გასწორდა და ფორმულირება გახდა თანამედროვე სახე: "ყოველი ლუწი რიცხვი, დაწყებული 4-ით, შეიძლება წარმოდგენილი იყოს როგორც ორი მარტივი რიცხვის ჯამი."
გავიხსენოთ განმარტება. მარტივი რიცხვი არის ბუნებრივი რიცხვი p, რომელსაც აქვს მხოლოდ 2 განსხვავებული ბუნებრივი გამყოფი: თავად p და 1. დასკვნა განმარტებიდან: მარტივ რიცხვს p აქვს მხოლოდ ერთი მარტივი გამყოფი - თავად p.
ახლა დავუშვათ, რომ 1 არის მარტივი რიცხვი. განმარტებით, მარტივ რიცხვს აქვს მხოლოდ ერთი მარტივი გამყოფი - თავად. შემდეგ გამოდის, რომ 1-ზე მეტი ნებისმიერი მარტივი რიცხვი იყოფა მისგან განსხვავებულ მარტივ რიცხვზე (1-ზე). მაგრამ ორი განსხვავებული მარტივი რიცხვი არ შეიძლება დაიყოს ერთმანეთზე, რადგან წინააღმდეგ შემთხვევაში ისინი არ არიან მარტივი რიცხვები, არამედ შედგენილი რიცხვები და ეს ეწინააღმდეგება განმარტებას. ამ მიდგომით, გამოდის, რომ არსებობს მხოლოდ 1 მარტივი რიცხვი - თავად ერთეული. მაგრამ ეს აბსურდია. ამიტომ, 1 არ არის მარტივი რიცხვი.
1, ისევე როგორც 0, ქმნიან რიცხვთა სხვა კლასს - ნეიტრალური ელემენტების კლასს n-არის მოქმედებებთან მიმართებაში ალგებრული ველის ზოგიერთ ქვეჯგუფში. უფრო მეტიც, შეკრების მოქმედებასთან დაკავშირებით, 1 ასევე არის მთელი რიცხვების რგოლის წარმომქმნელი ელემენტი.
ამ გათვალისწინებით, სხვა ალგებრულ სტრუქტურებში მარტივი რიცხვების ანალოგების აღმოჩენა არ არის რთული. დავუშვათ, გვაქვს 2-ის ხარისხებიდან ჩამოყალიბებული მრავლობითი ჯგუფი, დაწყებული 1-დან: 2, 4, 8, 16, ... და ა.შ. 2 აქ ფორმირების ელემენტად მოქმედებს. მარტივი რიცხვი ამ ჯგუფში არის რიცხვი, რომელიც აღემატება უმცირეს ელემენტს და იყოფა მხოლოდ საკუთარ თავზე და უმცირეს ელემენტზე. ჩვენს ჯგუფში მხოლოდ 4-ს აქვს ასეთი თვისებები. ჩვენს ჯგუფში აღარ არის მარტივი რიცხვები.
თუ 2 ასევე მარტივი რიცხვი იყო ჩვენს ჯგუფში, მაშინ იხილეთ პირველი აბზაცი - ისევ აღმოჩნდება, რომ მხოლოდ 2 არის მარტივი რიცხვი.