বড় কোন সংখ্যার Divisor কিভাবে বের করব? আমি 10^9 পর্যন্ত বের করতে পারছি, কিন্তু এর বড় হলেই আর আউটপুট আসছে না। তাছাড়া সিভ অ্যাল্গরিদম দিয়ে ও তো 10^6 এর বেশি বের করতে পারছি না। 10^12 পর্যন্ত কিভাবে বের করব Efficient পদ্ধতিটা জানতে চাঁই। My loop -

for(i=1; i*i <= n; i++){ if(n%i == 0){ v.push_back(i); if(i != n/i){ v.push_back(n/i); } } }

asked 04 Apr '16, 12:13

Tanmoy%20Roy's gravatar image

Tanmoy Roy
13410

edited 04 Apr '16, 14:26


একটু খেয়াল করলেই দেখতে পাবেন যেকোন নাম্বার এর Divisor তার squareroot/বর্গমুল এর মধ্যে থাকে। ১৬ এর জন্য যদি চিন্তা করি। তাহলে ১৬ এর squareroot হল ৪। আমার ১ থেকে ৪ পর্যন্ত একটি লুপ চালাবো। যেগুলা দিয়ে নিঃশেষে ভাগ যাবে আর যা পাবো ভাগফল হিসাবে তা সেভ করবো।

১৬ ১ দিয়ে ভাগ যায় । তাহলে পেলাম Ans= 1 16
১৬ ২ দিয়ে ভাগ যায় । তাহলে পেলাম Ans= 1 16 2 8
১৬ ৩ দিয়ে ভাগ যায় না ।
১৬ ৪ দিয়ে ভাগ যায় । তাহলে পেলাম Ans= 1 16 2 8 4 4

Ans অ্যারেতে ১৬ এর Divisor আছে।

তাহলে ১০^১২ এর জন্য ১০^৬ এর একটি লুপ চালাবো। আর ২ডি অ্যারে বা ভেক্টরে রেজাল্ট গুলো precalculated করে রাখবো।

permanent link

answered 05 Apr '16, 10:31

Kaiser%20Ahmed's gravatar image

Kaiser Ahmed
3.2k419

Your answer
toggle preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported

Question tags:

×4
×2

question asked: 04 Apr '16, 12:13

question was seen: 1,153 times

last updated: 05 Apr '16, 10:31