প্রাইম নাম্বার বের করার জন্য সিভের অ্যালগরিদম প্রায় সবাই জানে, অনেকের অ্যালগোরিদম শেখার শুরুটাও এই সিভ দিয়ে আমার নিজের তাই। যাই হোক প্রাইম নাম্বার চেক করার জন্য আর একটি সহজ থিওরি হচ্ছে এই উইসন থিওরেম।
উইলসন থিওরেমকে এভাবে বলা যায়, একটি 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 করা যায়,
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| #include<stdio.h> | |
| int main() | |
| { | |
| int n,m,i,p,fact; | |
| while(scanf("%d",&n)==1){ | |
| fact=1; | |
| m=n; | |
| for(i=1;i<=n-1;i++){ | |
| fact=(fact*i) %m; | |
| } | |
| if (fact==n-1) | |
| printf("%d is prime\n",n); | |
| else | |
| printf("%d is not prime\n",n); | |
| } | |
| return 0; | |
| } |
একটা বিষয় মাথায় রাখতে হবে অনেক বড় সংখ্যার প্রোগ্রামটি ক্ষেত্রে
একটু slow কাজ করতে পারে সেক্ষেত্রে আবার mod m অর্থাৎ fact=((fact*i) %m)%m; করতে হবে।
উইলসন থিওরেম এর প্রমাণ এই লিঙ্কে সুন্দর ভাবে দেওয়া আছে,কষ্ট
করে দেখে নিবেন।
তবে আমি একটু অন্যভাবে এইটা প্রমাণ করার চেষ্টা করছি, সেটা
হচ্ছে সিভের অ্যালগোরিদম দিয়ে 1 থেকে 10000000 পর্যন্ত প্রাইম নাম্বার
বের করি এবং একটা prime.txt ফাইলে সেভ করি তারপর উইলসন দিয়ে চেক করি প্রাইম
নাকি প্রাইম নয় এবং primeCheck.txt ফাইলে সেভ করি, এরকম
ভাবে,
একটা output দেখা যাক 10000000 পর্যন্ত ঠিকঠাক কাজ করতেছে।
লেখাটা বাংলিশ হয়ে গেল আশা করি ক্ষমা সুন্দর দৃষ্টিতে দেখবেন।
** আমার কোথাও ভুল হতে পারে,দয়া করে মন্তব্য করবেন।ভুল করার
প্রবনতাই মানুষকে অন্যান্য সৃষ্টি থেকে আলাদা করে।
