Fermat’s theorem -- (ফারমাট'স থেওরেম)

An Integer can be represented as the sum of two square number.

অর্থাৎ একটি integer সংখ্যাকে দুটি সংখ্যার বর্গের যোগফল হিসেবে প্রকাশ করা যায়।এটি একটি classical Math প্রবলেম। এটিকে আমরা এভাবে লিখতে পারি x = a²+b² ।

Fermat’s theorem এর সাহায্যে খুব সহজেই এটা বের করা যায়।

একটি সংখ্যা x কে দুটি পূর্ণ সংখ্যার বর্গের যোগফল হিসেবে প্রকাশ করা যাবে যদি ওই সংখ্যাটির (x) প্রাইম factorization এর প্রতিটি প্রাইম ফ্যাক্টর 4k+3 ফর্মে থাকে জোড় সংখ্যক বার।

যেমনঃ 147 এর প্রাইম factorization করলে এর প্রাইম ফ্যাক্টর গুলো পাওয়া যাবে 3,7,7

3 কে 4k+3 ফর্মে প্রকাশ করা যায় না।  

7 কে 4k+3 ফর্মে প্রকাশ করা যায় যেখানে k=1 (k>=1)। এবং 7 আছে দুই বার। তাই 147 কে দুটি সংখ্যার বর্গের যোগফল হিসেবে প্রকাশ করা যায়।

আর একটা উদাহরণ দেখা যাক,

42 = 2*3*7  এই প্রাইম ফ্যাক্টর গুলোর মধ্যে মাত্র 7 কে 4k+3 ফর্মে প্রকাশ করা যায়, 2 এবং 3 কে যায় না। তাই 47 কে কখনোই দুটি সংখ্যার বর্গের যোগফল হিসেবে প্রকাশ করা যাবে না।

Fermat’s Theorem :  কোন প্রাইম নাম্বারকে দুটি সংখ্যার বর্গের যোগফল হিসেবে প্রকাশ করা যাবে শুধুমাত্র যদি ওই প্রাইম নাম্বারকে 4 দিয়ে ভাগ করলে ভাগশেষ 1 থাকে (p = 1 (mod 4) ।(অথবা p কে যদি 4k+1 ফর্মে লেখা যায় তাহলেই একে p = a² + b²  ফর্মে লেখা যাবে ) 

Proof : এই লিঙ্কে

Read More

উইলসন থিওরেম

প্রাইম নাম্বার বের করার জন্য সিভের অ্যালগরিদম প্রায় সবাই জানে, অনেকের অ্যালগোরিদম শেখার শুরুটাও এই সিভ দিয়ে আমার নিজের তাই। যাই হোক প্রাইম নাম্বার চেক করার জন্য আর একটি সহজ থিওরি হচ্ছে এই উইসন থিওরেম।

উইলসন থিওরেমকে এভাবে বলা যায়, একটি natural number  n( n>1 )প্রাইম হবে যদি (( n-1)!) mod n =n-1 হয়।

এটাই হচ্ছে উইলসন থিওরেম।

(n-1) ! = 1*2*3*4*5*……………………*n-1 ;

একটা উদাহরণ দেওয়া যাক,

ধরা যাক n=6

(n-1)! mod n = 5! Mod 6 = 0

0 is not equal to n-1 = 5 , So n=6  is not prime .

Another Example :

Assume, n=7

(n-1)! mod n = 6! Mod 7 = 6

6 is equal to n-1 = 6 , So n=7  is prime .

এভাবে একে implement করা যায়,

একটা বিষয় মাথায় রাখতে হবে অনেক বড় সংখ্যার প্রোগ্রামটি ক্ষেত্রে একটু slow কাজ করতে পারে সেক্ষেত্রে আবার mod m অর্থাৎ fact=((fact*i) %m)%m;  করতে হবে।  

উইলসন থিওরেম এর প্রমাণ এই লিঙ্কে  সুন্দর ভাবে দেওয়া আছে,কষ্ট করে দেখে নিবেন।

তবে আমি একটু অন্যভাবে এইটা প্রমাণ করার চেষ্টা করছি, সেটা হচ্ছে সিভের অ্যালগোরিদম দিয়ে 1 থেকে 10000000 পর্যন্ত প্রাইম নাম্বার বের করি এবং একটা prime.txt ফাইলে সেভ করি তারপর উইলসন দিয়ে চেক করি প্রাইম নাকি প্রাইম নয় এবং primeCheck.txt ফাইলে সেভ করি, এরকম ভাবে,  

একটা output দেখা যাক 10000000 পর্যন্ত ঠিকঠাক কাজ করতেছে। 

আপনারা চাইলে এখান থেকে পোস্টটি txt ফাইল সহ  PDF Download করে নিতে পারেন।

লেখাটা বাংলিশ হয়ে গেল আশা করি ক্ষমা সুন্দর দৃষ্টিতে দেখবেন।

** আমার কোথাও ভুল হতে পারে,দয়া করে মন্তব্য করবেন।ভুল করার প্রবনতাই মানুষকে অন্যান্য সৃষ্টি থেকে আলাদা করে। 

Read More

Uva 10394 (Twin primes)

Solution : 




input :

10
100
1000
10000
100000

output :

Read More

Prime Factoraization

Prime Factorization বলতে সহজ কথায় কোন সংখ্যার প্রাইম ফ্যাক্টর গুলো বোঝায়। আপনাকে এমন একটি প্রোগ্রাম লিখতে হবে যেটি কিনা যেকোনো সংখ্যার প্রাইম ফ্যাক্টর গুলো বের করে দিবে। এই পোস্টটি পড়ার আগে আপনাকে প্রাইম নাম্বার বের করার সিভের অ্যালগরিদমটি জানা থাকতে হবে না হলে সব নেটওয়ার্ক এর উপর দিয়ে যাবে।
একটা পূর্ণ সংখ্যাকে আমরা এভাবে represent করতে পারি
40=2^3*5
দেখুন সব প্রাইম নাম্বার কেননা যৌগিক সংখ্যা মাত্রই কত গুলো মৌলিক সংখ্যার সমষ্টি।
কোন যৌগিক সংখ্যার বর্গমূলের সমান বা ছোট কত গুলো প্রাইম ফ্যাক্টর থাকবেই (সিভের অ্যালগরিদম)। এটাই হচ্ছে prime factorization এর মূল বিষয়।

sqrt(114)=10
তাহলে 114 এরে প্রাইম ফ্যাক্টর গুলো ২ - ১০ এর মধ্যেই থাকবে এর বাইরে যাবে না । আমাদের কাজ হচ্ছে ২-১০ পর্যন্ত যতগুলো  প্রাইম নাম্বার আছে সেগুলো দিয়ে ১১৪ কে ভাগ করে দেখা যদি ভাগশেষ শূন্য হয় তাহলে তাহলে ওই সংখ্যাটি ১১৪ এর প্রাইম ফ্যাক্টর এভাবে ১০ পর্যন্ত চেক করা এর পর

114 = (114/2) = 57 , NOW, 57 / 3 = 19, Then, 19. 19 is prime so no need to check 

 So, 2*3*19.  is the prime factor of 114. 

Prime Factorization Flow chart

আরেক ভাবে প্রাইম ফ্যাক্টর গুলো বের করা যায়, একটা array তে N পর্যন্ত সব প্রাইম নাম্বার বের করে রেখে যে সংখ্যার প্রাইম ফ্যাক্টর গুলো বের করবো সেই সংখ্যার বর্গমূল পর্যন্ত ফ্যাক্টরগুলো বের করে আগের বের করে রাখা প্রাইম array এর সাথে চেক করা। উপরে একটা flow chart আছে নিজেরা চেষ্টা করতে পারেন আর আমি সময় পেলে কোডটা পোস্ট করে দিব।

Read More

UVA Problem -- 10235

Problem Name :  Simply Emirp

Problem Link 

প্রবলেমটা অসাধারণ !! । আপনাকে palindromic prime নাম্বার গুলাকে প্রাইম প্রিন্ট দিতে হবে এটাই Tricky এই প্রবলেমে।

Read More

UVA Problem # 686 ( Goldbach's Conjecture (II))

Problem Link : UVA Problem # 686 ( Goldbach's Conjecture (II))

প্রবলেমটা খুব সহজ কিন্তু আমার বার বার runtime error দেখাইতেছিল মাথা নষ্ট হওয়ার মতো  অবস্থা পরে বুঝতে পারলাম আমার সিভের অ্যালগরিদমে prime Array ঠিক ভাবে declare করা হয় নাই কিন্তু আমি প্রথমেই ওইটাকে ঠিক ধরে নিয়ে বাকি গুলা চেক করছিলাম।

যাই হোক প্রবলেমটা সল্ভ করে মজা পাইছি, 

Solution টা ঠিক আছে নাকি -ইনপুট আউট চেক করার জন্য নিচের input-output গুলো ব্যাবহার করা যেতে পারে ।

input ---> output 

22292 ---> 177 
30000 ---> 602 
32000 ---> 312 
100 ---> 6 
20 ---> 2 

598 ---> 15

2222 ----> 35

Read More