Number of Coprime / Relatively prime


একটি সংখ্যার co prime / relatively prime এর সংখ্যা :

২টি সংখ্যার মধ্যে যদি, ১ ছাড়া কোন সাধারন গুণনীয়ক না থাকে তবে তারা co prime / relatively prime

যেমন : ৪ এবং ৯ । এরা একে অন্যের co prime / relatively prime
১২ এবং ১৮ এদের মধ্যে সাধারন গুণনীয়ক : , , , ৬ । সুতরাং এরা co prime নয় ।

নির্দিষ্ট করে বলতে গেলে, ১২ এর co prime গুলো হচ্ছে : , , , ১১
অর্থ্যাৎ, ১২ থেকে ছোট যে সংখ্যাগুলো সাথে ১২র কোন সাধারন গুণনীয়ক নাই, তারা ১২co prime

অন্যভাবে বলতে গেলে, gcd (x, 12) = 1 হলে, x হল ১২co prime
gcd (greatest common divisor) =
গরিষ্ঠ সাধারন গুণনীয়ক

numberOfCoprime = 0;

for ( k = 1; k < x; k++ ) {
	if ( gcd (k, x) == 1 )
		numberOfCoprime++;
}

x যদি বড় হয় তাহলে এই কোডটা আউটপুট দিতে অনেক সময় নিবে ।
অথবা অনেকগুলো ছোট ছোট x এর coprime বের করতেও সময় লাগবে ।

একটা কাজ করা যায়,
প্রথমে x’র প্রাইম ফ্যাক্টরগুলো বের করতে হবে । মানে, সংখ্যাটিকে প্রাইম সংখ্যার গুনফল আকারে প্রকাশ করতে হবে ।

যেমন : ১২ = * * = * ৩ ।
আমাদের শুধু প্রাইম সংখ্যাগুলো প্রয়োজন। মানে, ২ এবং ৩

সূত্রটা এমন, x * (1 – 1 / prime1) * (1 – 1 / prime2) * (1 – 1 / prime3) * …..

১২র জন্য হবে,

numberOfCoprime = 12 * (1 – 1 / 2) * (1 – 1 / 3)

=> 12 * (½) * (2/3)

=> 24 / 6

=> 4

একইভাবে 210′র জন্য করা যাক,

210 = 2 * 3 * 5 * 7

numberOfCoprime = 210 * (1 – 1 / 2) * (1 – 1 / 3) * (1 – 1 / 5) * (1 – 1 / 7)

=> 210 * (½) * (2/3) * (4/5) * (6/7)

=> 10080 / 210

=> 48

এখন প্রশ্ন হল, কোন সংখ্যার প্রাইম ফ্যক্টর কিভাবে বের করতে হয় ?
এটা না হয় অন্যদিনের জন্য থাকুক ..

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s