Prime Factor Division CodeChef Solution

Problem -Prime Factor Division CodeChef Solution

This website is dedicated for CodeChef solution where we will publish right solution of all your favourite CodeChef problems along with detailed explanatory of different competitive programming concepts and languages.

Prime Factor Division CodeChef Solution in C++17

#include <bits/stdc++.h>
using namespace std;

int main() {
	// your code goes here
	int t; cin>>t;
	while(t--){
	    long long int  a,b;
	    cin>>a>>b;
	    long long int  g=__gcd(a,b);;
	    while(b!=1){
	        g=__gcd(a,b);
	        
	        b=b/g;
	        if(g==1){
	            break;
	        }
	    }
	    if(g==1 && b!=1){
	        cout<<"NO"<<endl;
	    }else{
	        cout<<"YES"<<endl;
	    }
	}
	return 0;
}

Prime Factor Division CodeChef Solution in C++14

#include <bits/stdc++.h>
//for policy based ds //p.order_of_key() -> returns index of value //*p.find_by_order(3) ->value at index
#include <ext/pb_ds/assoc_container.hpp> // Common file
#include <ext/pb_ds/tree_policy.hpp>
#include <functional> // for less

using namespace __gnu_pbds; //for policy based ds
using namespace std;

#define int long long
#define pii pair<int, int>
#define vi vector<int>
#define maxHeap priority_queue<int>;
#define minHeap priority_queue<int, vi, greater<int>>
#define mod 1000000007
#define inf 1e18
#define rep(i, s, n) for (int i = s; i < n; i++)
#define sp(ans, pre) fixed << setprecision(pre) << y
#define pb push_back
#define srt(v) sort(v.begin(), v.end())
#define all(v) begin(v), end(v)
#define inputArr(i, arr) \
    for (int &i : arr)   \
        cin >> i;
#define ll long long
#define ull unsigned long long
#define lld long double
#define kickPrint(tt) cout << "Case #" << tt << ": "

typedef tree<pii, null_type, less<pii>, rb_tree_tag, tree_order_statistics_node_update> pbds;

time_t Begin;

//////////////////Debug///////////////
#define debug(x)       \
    cout << #x << " "; \
    _print(x);         \
    cout << endl;
void _print(ll t)
{
    cout << t;
}
//void _print(int t) {cout << t;}
void _print(string t) { cout << t; }
void _print(char t) { cout << t; }
void _print(lld t) { cout << t; }
void _print(double t) { cout << t; }
void _print(ull t) { cout << t; }
void display(ll a[], ll n)
{
    for (ll i = 0; i < n; i++)
    {
        cout << a[i] << " ";
    }
    cout << endl;
}

template <class T, class V>
void _print(pair<T, V> p);
template <class T>
void _print(vector<T> v);
template <class T>
void _print(set<T> v);
template <class T, class V>
void _print(map<T, V> v);
template <class T>
void _print(multiset<T> v);
template <class T, class V>
void _print(pair<T, V> p)
{
    cout << "{";
    _print(p.ff);
    cout << ",";
    _print(p.ss);
    cout << "}";
}
template <class T>
void _print(vector<T> v)
{
    cout << "[ ";
    for (T i : v)
    {
        _print(i);
        cout << " ";
    }
    cout << "]";
}
template <class T>
void _print(set<T> v)
{
    cout << "[ ";
    for (T i : v)
    {
        _print(i);
        cout << " ";
    }
    cout << "]";
}
template <class T>
void _print(multiset<T> v)
{
    cout << "[ ";
    for (T i : v)
    {
        _print(i);
        cout << " ";
    }
    cout << "]";
}
template <class T, class V>
void _print(map<T, V> v)
{
    cout << "[ ";
    for (auto i : v)
    {
        _print(i);
        cout << " ";
    }
    cout << "]";
}
template <typename T, typename U>
inline bool chmax(T &a, U b) { return a < b ? (a = b, true) : false; }
template <typename T, typename U>
inline bool chmin(T &a, U b) { return a > b ? (a = b, true) : false; }

void init()
{
    Begin = clock();
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
#ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif
}
void timeTaken()
{
#ifndef ONLINE_JUDGE
    double time_taken = double(clock() - Begin) / double(CLOCKS_PER_SEC);
    cout << "Execution Time: " << fixed << setprecision(5) << time_taken << "s\n";
#endif
}

vector<int> computeLps(string s, int M)
{
    int len = 0;
    vector<int> lps(M + 20);

    lps[0] = 0;

    int i = 1;
    while (i < M)
    {
        if (s[i] == s[len])
        {
            len++;
            lps[i] = len;
            i++;
        }
        else
        {
            if (len != 0)
            {
                len = lps[len - 1];
            }
            else
            {
                lps[i] = 0;
                i++;
            }
        }
    }
    // debug(len);
    return lps;
}

int ceiling(int x, int y)
{
    int res = x / y;
    if (x % y)
    {
        if (x >= 0)
            res++;
    }
    return res;
}

vector<vector<int>> makePrefix(vector<vector<int>> &grid)
{
    int n = grid.size(), m = grid[0].size();
    vector<vector<int>> prefix(n + 1, vector<int>(m + 1));

    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < m; j++)
        {
            prefix[i + 1][j + 1] = grid[i][j] + prefix[i][j + 1] + prefix[i + 1][j] - prefix[i][j];
        }
    }

    return prefix;
}

int query(int x1, int y1, int x2, int y2, vector<vector<int>> &prefix)
{
    // cout << x1 << " " << y1 << " " << x2 << " " << y2 << endl;

    // cout << "query: " << prefix[x2 + 1][y2 + 1] << " " << prefix[x2 + 1][y1] << " " << prefix[x1][y2 + 1] << " " << prefix[x1][y2] << endl;
    return prefix[x2 + 1][y2 + 1] - prefix[x2 + 1][y1] - prefix[x1][y2 + 1] + prefix[x1][y1];
}

int toInt(string &s)
{
    int res = 0;
    for (char c : s)
        res = res * 10 + (c - '0');
    return res;
}

bool isValid(int i, int j, int n, int m)
{
    return i >= 0 && i < n && j >= 0 && j < m;
}

int dx[] = {-1, 0, 0, 1};
int dy[] = {0, 1, -1, 0};

int moduloExponentiation(int a, int b, int m)
{
    if (b == 0)
        return 1;

    int res = moduloExponentiation(a, b / 2, m);
    res = (res * res) % m;

    if (b % 2)
        res = (res * a) % m;
    return res;
}

int32_t main()
{
    init();
    //--------------------
    int t = 1;
    cin >> t;
    for (int tt = 1; tt <= t; tt++)
    {
        int a, b;
        cin >> a >> b;
        int pre = b;
        while (b != 1)
        {
            int g = __gcd(a, b);
            b /= g;
            if (b == pre)
                break;
            pre = b;
        }

        cout << (b == 1 ? "YES\n" : "NO\n");
    }
    //---------------------------
    timeTaken();
    return 0;
}

Prime Factor Division CodeChef Solution in PYTH 3

# cook your dish here
import math
n=int(input())
for i in range(1,n+1):
    a,b=map(int,input().split())
    c=0
    d=pow(a,max(a,b),b)
    if(d==0):
        print("YES")
    else:
        print("NO")

Prime Factor Division CodeChef Solution in C

#include <stdio.h>

// C++ program to find GCD of two numbers

// Recursive function to return gcd of a and b in single line
long high1(long num1, long  num2)
{
 return num2== 0 ? num1: high1(num2, num1 % num2); 
}


int main() 
{
    int test;
    scanf("%d",&test);
    for(int i=0;i<test;i++)
    {
        long  num1,num2;
        scanf("%ld %ld",&num1,&num2);
        long maths = high1(num1,num2);
        while(maths!=1)
        {
            num2/=maths;
            maths = high1(maths,num2);
        }
        if(num2!=1){
            printf("NO \n");
        }
        else
        printf("YES \n");
        
    }
 
 return 0;
}

Prime Factor Division CodeChef Solution in JAVA

 import java.io.*;
import java.util.*;
 class Codechef
 {  
	

	static void BFS(ArrayList<ArrayList<Integer>> adj,int s, boolean[] visited) 
	{ 
    	Queue<Integer> q=new LinkedList<>();
    	
    	visited[s] = true; 
    	q.add(s); 
    
    	while(q.isEmpty()==false) 
    	{ 
    		int u = q.poll(); 
    		 
    		for(int v:adj.get(u)){
    		    if(visited[v]==false){
    		        visited[v]=true;
    		        q.add(v);
    		    }
    		} 
    	} 
	} 
	static int BFS(ArrayList<ArrayList<Integer>> adj,pair s, boolean[] visited,int ar[],int m) 
	{ 
    	Queue<pair> q=new LinkedList<>();
    	
    	visited[s.a] = true; 
    	q.add(s); 
    
		int count=0;
    	while(q.isEmpty()==false) 
    	{ 
    		pair u = q.poll(); 
			// if(adj.get(u.a).size()==0)
			// count++;
	 
			boolean end=true;
    		for(int v:adj.get(u.a)){
    		    if(visited[v]==false){
    		        visited[v]=true;
					end=false;
					int cat=ar[v]==0?0:ar[v]+u.b;
					if(cat>m)
					continue;
    		        q.add(new pair(v, cat));
					// System.out.print("--"+v+" "+cat+"--");
    		    }
    		} 
			if(end)
			count++;
			// System.out.println(u.a+" "+adj.get(u.a).size()+" count "+count);
    	} 
		return count;
	} 
	static void addEdge(ArrayList<ArrayList<Integer>> adj, int u, int v) 
	{ 
		adj.get(u).add(v); 
		adj.get(v).add(u); 
	} 
	static void ruffleSort(long[] a) {
        int n=a.length;
		Random random = new Random();
        for (int i=0; i<n; i++) {
            int oi=random.nextInt(n);
			long temp=a[oi];
            a[oi]=a[i]; a[i]=temp;
        }
        Arrays.sort(a);
    }
	static void ruffleSort(int[] a) {
        int n=a.length;
		Random random = new Random();
        for (int i=0; i<n; i++) {
            int oi=random.nextInt(n);
			int temp=a[oi];
            a[oi]=a[i]; a[i]=temp;
        }
        Arrays.sort(a);
    }
	public static int Lcm(int a,int b)
	{ int max=Math.max(a,b);
		for(int i=1;;i++)
		{
			if((max*i)%a==0&&(max*i)%b==0)
			return (max*i);
		}
 
	}
  static void sieve(int n,boolean prime[])
    {
       
        // boolean prime[] = new boolean[n + 1];
        for (int i = 0; i <= n; i++)
            prime[i] = true;
 
        for (int p = 2; p * p <= n; p++) {
            
            if (prime[p] == true) {
               
                for (int i = p * p; i <= n; i =i+ p)
                    prime[i] = false;
            }
        }
 
        
    }
 
	// public static String run(int ar[],int n)
	// { 
			
	// }
	
	
	public static int upperbound(int s,int e, long ar[],long x)
	{
		int res=-1;
		while(s<=e)
		{ int mid=((s-e)/2)+e;
			if(ar[mid]>x)	
			{e=mid-1;res=mid;}
			else if(ar[mid]<x)
			{s=mid+1;}
			else
			{e=mid-1;res=mid;
			 if(mid>0&&ar[mid]==ar[mid-1])
			 e=mid-1;
			 else
			 break;
			}

		}
		return res;
	}
	public static long lowerbound(int s,int e, long ar[],long x)
	{
		long res=-1;
		while(s<=e)
		{ int mid=((s-e)/2)+e;
			if(ar[mid]>x)	
			{e=mid-1;}
			else if(ar[mid]<x)
			{s=mid+1;res=mid;}
			else
			{res=mid;
				if(mid+1<ar.length&&ar[mid]==ar[mid+1])
			    s=mid+1;
			    else
				break;}

		}
		return res;
	}
	
	static long modulo=1000000007;
	public static long power(long a, long b)
	{
		if(b==0) return 1;
		long temp=power(a,b/2)%modulo;
		
		if((b&1)==0)
		return (temp*temp)%modulo;
		else 
		return (((temp*temp)%modulo)*a)%modulo;
	}
	public static long powerwithoutmod(long a, long b)
	{
		if(b==0) return 1;
		long temp=power(a,b/2);
		
		if((b&1)==0)
		return (temp*temp);
		else 
		return ((temp*temp)*a);
	}
	public static double log2(long a)
	{ double d=Math.log(a)/Math.log(2);
		return d;

	}
	public static int log10(long a)
	{ double d=Math.log(a)/Math.log(10);
		return (int)d;

	}
	
	public static long gcd(long a, long b)
    {
        if (a == 0)
            return b;
 
        return gcd(b % a, a);
    }
	
	public static void tree(int s,int e,int ar[],int c)
	{
	  if(s<=e)
	  {
		  int max=s;
		  for(int i=s;i<=e;i++)
		   if(ar[i]>ar[max])
			 max=i;
			 
		  ar[max]=c++;
		  tree(s,max-1,ar,c);
		  tree(max+1,e,ar,c);
	  }
	}
	
 static int resturant=0;
 static void DFS(ArrayList<ArrayList<Integer>> al,boolean visited[],int s,int max,int curr,int ar[])
 {
	
	visited[s]=true;
	if(al.get(s).size()==1&&visited[al.get(s).get(0)]==true)
	{resturant++;return;}
	// System.out.println(s+" "+curr);
	for(int x:al.get(s))
	{
		if(visited[x]==false)
		{
			if(ar[x]==0)
			DFS(al, visited, x, max, 0, ar);
			else if(curr+ar[x]<=max)
			DFS(al, visited, x, max, curr+ar[x], ar);
			
		}
	}
	
 }
 static int solve(long a,long b)
 {
	if(b==1)
	return 1;
	long gcd=gcd(a, b);
	if(gcd==1)
	return -1;
	return solve(a,b/gcd);
 }
	
	public static void main(String[] args) throws Exception
   {
		FastIO sc = new FastIO();
		
 
		//sc.println();
//xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx CODE xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
		int test=sc.nextInt();
		
		// // double c=Math.log(10);
		// boolean prime[]=new boolean[233334];
		// sieve(233334, prime);
		// HashMap<Character,Integer> hm=new HashMap<>(9);
		// char c='1';
		// for(int i=1;i<=9;i++)
		//  hm.put(c++,i);

		

		while(test-->0)
		{
		
		
		  
		long a=sc.nextLong();
		long b=sc.nextLong();
		if(b==1)
		{
			sc.println("YES");
			continue;
		}
		
		int res=solve(a,b);
		if(res==1)
		sc.println("YES");
		else 
		sc.println("NO");
		

		

		
		
	

		






		}
				
	
	   
// xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx CODE xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
sc.close();	
}	
}


class pair implements Comparable<pair>{
	int a;
	int b;
	pair(int a,int b)
	{this.a=a;
		this.b=b;

	}
	public int compareTo(pair p)
	{
		
		return (this.b-p.b);
	}
}
class triplet implements Comparable<triplet>{
	int first,second,third;
	triplet(int first,int second,int third)
	{this.first=first;
		this.second=second;
		this.third=third;

	}
	public int compareTo(triplet p)
	{ if(this.third-p.third==0)
		return this.first-p.first;
		else
		return -this.third+p.third;
	}
}
// class triplet
// {
// 	int x1,x2,i;
// 	triplet(int a,int b,int c)
// 	{x1=a;x2=b;i=c;}
// }
 class FastIO extends PrintWriter {
	private InputStream stream;
	private byte[] buf = new byte[1<<16];
	private int curChar, numChars;
 
	// standard input
	public FastIO() { this(System.in,System.out); }
	public FastIO(InputStream i, OutputStream o) {
		super(o);
		stream = i;
	}
	// file input
	public FastIO(String i, String o) throws IOException {
		super(new FileWriter(o));
		stream = new FileInputStream(i);
	}
 
	// throws InputMismatchException() if previously detected end of file
	private int nextByte() {
		if (numChars == -1) throw new InputMismatchException();
		if (curChar >= numChars) {
			curChar = 0;
			try {
				numChars = stream.read(buf);
			} catch (IOException e) {
				throw new InputMismatchException();
			}
			if (numChars == -1) return -1; // end of file
		}
		return buf[curChar++];
	}
 
	public String nextLine() {
		int c; do { c = nextByte(); } while (c <= '\n');
		StringBuilder res = new StringBuilder();
		do { res.appendCodePoint(c); c = nextByte(); } while (c > '\n');
		return res.toString();
	}
 
	public String next() {
		int c; do { c = nextByte(); } while (c <= ' ');
		StringBuilder res = new StringBuilder();
		do { res.appendCodePoint(c); c = nextByte(); } while (c > ' ');
		return res.toString();
	}
 
	public int nextInt() { 
		int c; do { c = nextByte(); } while (c <= ' ');
		int sgn = 1; if (c == '-') { sgn = -1; c = nextByte(); }
		int res = 0;
		do {
			if (c < '0' || c > '9')
				throw new InputMismatchException();
			res = 10*res+c-'0';
			c = nextByte();
		} while (c > ' ');
		return res * sgn;
	}
 
  public long nextLong() { 
		int c; do { c = nextByte(); } while (c <= ' ');
		long sgn = 1; if (c == '-') { sgn = -1; c = nextByte(); }
		long res = 0;
		do {
			if (c < '0' || c > '9')
				throw new InputMismatchException();
			res = 10*res+c-'0';
			c = nextByte();
		} while (c > ' ');
		return res * sgn;
	}
 
	public double nextDouble() { return Double.parseDouble(next()); }
}

Prime Factor Division CodeChef Solution in PYPY 3

def gcd(m, n):
    if m%n==0:
        return n
    return gcd(n, m%n)

for i in range(int(input())):
    a, b = map(int, input().split())
    ans = "YES"
    while True:
        m = gcd(a, b)
        if m==b:
            break
        elif m==1:
            ans = "NO"
            break
        b = b//m
    print(ans)

Prime Factor Division CodeChef Solution in GO

package main

import (
	"bufio"
	"bytes"
	"fmt"
	"os"
)

func main() {
	reader := bufio.NewReader(os.Stdin)

	var buf bytes.Buffer

	tc := readNum(reader)

	for tc > 0 {
		tc--
		s, _ := reader.ReadBytes('\n')
		var A, B uint64
		pos := readUint64(s, 0, &A)
		readUint64(s, pos+1, &B)
		res := solve(int64(A), int64(B))
		if res {
			buf.WriteString("YES\n")
		} else {
			buf.WriteString("NO\n")
		}
	}

	fmt.Print(buf.String())
}

func readUint64(bytes []byte, from int, val *uint64) int {
	i := from

	var tmp uint64
	for i < len(bytes) && bytes[i] >= '0' && bytes[i] <= '9' {
		tmp = tmp*10 + uint64(bytes[i]-'0')
		i++
	}
	*val = tmp

	return i
}

func readInt(bytes []byte, from int, val *int) int {
	i := from
	sign := 1
	if bytes[i] == '-' {
		sign = -1
		i++
	}
	tmp := 0
	for i < len(bytes) && bytes[i] >= '0' && bytes[i] <= '9' {
		tmp = tmp*10 + int(bytes[i]-'0')
		i++
	}
	*val = tmp * sign
	return i
}

func readString(reader *bufio.Reader) string {
	s, _ := reader.ReadString('\n')
	for i := 0; i < len(s); i++ {
		if s[i] == '\n' || s[i] == '\r' {
			return s[:i]
		}
	}
	return s
}

func readNum(reader *bufio.Reader) (a int) {
	bs, _ := reader.ReadBytes('\n')
	readInt(bs, 0, &a)
	return
}

func readTwoNums(reader *bufio.Reader) (a int, b int) {
	res := readNNums(reader, 2)
	a, b = res[0], res[1]
	return
}

func readThreeNums(reader *bufio.Reader) (a int, b int, c int) {
	res := readNNums(reader, 3)
	a, b, c = res[0], res[1], res[2]
	return
}

func readNNums(reader *bufio.Reader, n int) []int {
	res := make([]int, n)
	x := 0
	bs, _ := reader.ReadBytes('\n')
	for i := 0; i < n; i++ {
		for x < len(bs) && (bs[x] < '0' || bs[x] > '9') && bs[x] != '-' {
			x++
		}
		x = readInt(bs, x, &res[i])
	}
	return res
}

func solve(A, B int64) bool {
	if A%B == 0 {
		return true
	}
	g := gcd(A, B)
	// S(g) == S(B)
	x := B / g

	for x > 1 {
		if g%x == 0 {
			return true
		}
		y := gcd(g, x)
		if y == 1 {
			break
		}
		x /= y
	}
	return false
}

func gcd(a, b int64) int64 {
	for b > 0 {
		a, b = b, a%b
	}
	return a
}
Prime Factor Division CodeChef Solution Review:

In our experience, we suggest you solve this Prime Factor Division CodeChef Solution and gain some new skills from Professionals completely free and we assure you will be worth it.

If you are stuck anywhere between any coding problem, just visit Queslers to get the Prime Factor Division CodeChef Solution.

Find on CodeChef

Conclusion:

I hope this Prime Factor Division CodeChef Solution would be useful for you to learn something new from this problem. If it helped you then don’t forget to bookmark our site for more Coding Solutions.

This Problem is intended for audiences of all experiences who are interested in learning about Programming Language in a business context; there are no prerequisites.

Keep Learning!

More Coding Solutions >>

Cognitive Class Answer

CodeChef Solution

Microsoft Learn

Leave a Reply

Your email address will not be published. Required fields are marked *