আলোচনাঃ
আমরা জানি, সব সংখ্যাই prime number দিয়ে ভাগ যায়। তো একটা সংখ্যা যদি একের বেশি prime number দিয়ে ভাগ যায় তাহলে সব থেকে বড় prime divisor টা বের করা লাগবে। 100 এর কথাই ভাবা যাক, 100 এর prime divisor 2,5 ।এখানে 5 বড় তাই 5 print করা লাগবে।
উত্তরঃ
তো এখানে যেহেতু সব থেকে বড় prime divisor টা বের করা লাগবে,তাই আমরা কোনো একটা নম্বর(N) এর সব prime divisor কে vector বা array তে রাখতে পারি। তাহলে সুবিধাটা হচ্ছে যে, আমরা জানি , prime divisor গুলোকে vector এ রাখলে সেগুলো sorted আকারেই push হতে থাকবে। উপরের চিত্র থেকেই আমরা তা
দেখতে পাচ্ছি। তাই সব থেকে বড় prime divisor টা vector এর সব থেকে শেষের index এ থাকবে সেটা নিশ্চিতভাবে বলা যায় (যদি vector এর size>1 হয় )।আর size=1/0 হলে -1 print করব।মনে আসতে পারে যে,size আবার 0 হবে কখন?
N=1 হলে চিন্তা করে দেখেন তো size কত হতে পারে?
আর প্রশ্নে বলা আছে, N এ সর্বোচ্চ 14 টা digit থাকতে পারে। N positive or negative এমন কিছু বলা নাই। যেহেতু বলা নাই তাই আমাদের negative number নিয়েও ভাবা লাগবে। Negative number থাকলে আমরা একে -1 দিয়ে গুণ করে positive করে দিব।কেন?
কারণ মনে করেন, N= -100. তাহলে -100 এর (খাতা কলমে) prime divisor হবে 2, 5.কিন্তু আমাদের program এর 10 no line আর 22 no line এর কোনো শর্তে কি এটা চলবে? 10 no line এ 2*2<= – 100 হবে।যা মিথ্যা। আবার 22 no line এও হয় -100>1 . এটাও মিথ্যা। কিন্তু সঠিক উত্তর হবে 5. তাই N কে positive করে নিলে আর এই সমস্যা হবে না।
C++ Code:
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e7;
vector<ll> prime,factor;
bool vis[100000000];
void divCount(ll n){
for(ll i=0;i<prime.size() && prime[i]*prime[i]<=n;i++){
if(n%prime[i]==0){
while(n%prime[i]==0){
n/=prime[i];
}
factor.push_back(prime[i]);
}
}
if(n>1){
factor.push_back(n);
}
}
void sieve(){
for(ll i=3;i*i<=N;i+=2){
if(vis[i]==0){
for(ll j=i*i;j<=N;j+=2*i){
vis[j]=1;
}
}
}
prime.push_back(2);
for(ll i=3;i<=N;i+=2){
if(vis[i]==0) prime.push_back(i);
}
}
int main(){
sieve();
ll n,cnt=0,mx=0;
while(cin>>n){
if(n==0) break;
else{
if(n<0){
n=n*(-1);
}
divCount(n);
if(factor.size()>1){
printf("%lld\n",factor[factor.size()-1]);
}
else{
printf("-1\n");
}
}
factor.clear();
}
return 0;
}