Archive for the ‘Prime numbers’ Category

UVA – 12396 – Remoteland   Leave a comment


A number has is a perfect square if and only if all the powers of it’s prime factors are even.

#include <iostream>
#include <algorithm>
#include <vector>
#include <bitset>
#include <stdio.h>
using namespace std;
#define N 10000005
#define MOD 1000000007
typedef long long ll;
bitset<N> parity;
int pfactor[N];
int res[N];
void calc() {
	parity.reset();
	for (int i = 0; i < N; i++)
		pfactor[i] = 0;
	pfactor[0] = pfactor[1] = -1;
	for (int i = 2; i * i < N; i++) {
		if (!pfactor[i])
			for (int j = i * i; j < N; j += i)
				pfactor[j] = i;
	}

	for (int i = 2; i < N; i++)
		if (!pfactor[i])
			pfactor[i] = i;
	res[0] = res[1] = 1;
	for (int i = 2; i < N; i++) {
		ll current = res[i - 1];
		int k = i;
		while (pfactor[k] != -1) {
			parity.flip(pfactor[k]);
			if (!parity[pfactor[k]]) {
				current = (current * pfactor[k]) % MOD;
				current = (current * pfactor[k]) % MOD;
			}
			k /= pfactor[k];
		}
		res[i] = (int) current;
	}
}
int main() {
	calc();
	while (1) {
		int n;
		scanf("%d", &n);
		if (!n)
			break;
		cout << res[n] << endl;

	}
	return 0;
}

Posted August 5, 2012 by epicrado in Mathematics, Prime numbers

UVA – 10527 – Persistent Numbers   Leave a comment


import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.math.BigInteger;

public class PNumbers {
	public static void main(String[] args) throws Exception {
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		while (true) {
			String s = in.readLine();
			if (s.equals("-1"))
				break;
			if (s.length() == 1)
				System.out.println("1" + s);
			else {
				int[] a = new int[10];
				BigInteger n = new BigInteger(s);
				int tot = 0;
				for (int i = 9; i > 1; i--) {
					BigInteger ii = new BigInteger(i + "");
					while (n.mod(ii).equals(BigInteger.ZERO)) {
						n = n.divide(ii);
						a[i]++;
						tot++;
					}
				}
				if (!n.equals(BigInteger.ONE))
					System.out.println("There is no such number.");
				else {
					char[] res = new char[tot];
					tot = 0;
					for (int i = 2; i <= 9; i++)
						while (a[i] > 0) {
							a[i]--;
							res[tot++] = (char) (i + '0');
						}
					System.out.println(new String(res));
				}
			}
		}
	}
}

Posted March 19, 2012 by epicrado in ad-hoc, Mathematics, Prime numbers

UVA – 11086 – Composite Prime   Leave a comment


Since M is the set of composites,Then only those numbers having 2 prime factors are the composite primes ( as M contains no primes ).
We used prime factor counting method explained here.

import java.util.Scanner;

public class CompositePrimes {
	public static void main(String[] args) {
		int MAXN = (1 << 20) + 1;
		int primeFactor[] = new int[MAXN];
		for (int i = 2; i * i < MAXN; i++)
			if (primeFactor[i] == 0)
				for (int j = i * i; j < MAXN; j += i)
					primeFactor[j] = i;
		for (int i = 2; i < MAXN; i++)
			if (primeFactor[i] == 0)
				primeFactor[i] = i;
		int[] nPrimeFactors = new int[MAXN];
		nPrimeFactors[0] = nPrimeFactors[1] = 0;
		for (int i = 2; i < MAXN; i++)
			nPrimeFactors[i] = 1 + nPrimeFactors[i / primeFactor[i]];
		Scanner in = new Scanner(System.in);
		while (in.hasNext()) {
			int n = in.nextInt();
			int count = 0;
			for (int i = 0; i < n; i++)
				if (nPrimeFactors[in.nextInt()] == 2)
					count++;
			System.out.println(count);
		}

	}
}

Posted February 10, 2012 by epicrado in Prime numbers

UVA – 11426 – GCD – Extreme (I)   Leave a comment


import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.TreeSet;

public class GCDExtreme {
	public static void main(String[] args) throws NumberFormatException,
			IOException {
		long[] g = new long[200001];
		for (int i = 2; i < g.length; i++) {
			g[i] = g[i - 1];
			TreeSet<Integer> factors = new TreeSet<Integer>();

			for (int j = 1; j * j <= i; j++)
				if (i % j == 0) {
					factors.add(j);
					factors.add(i / j);
				}
			int[] arr = new int[factors.size()];
			int[] vals = new int[factors.size()];
			int t = 0;
			for (int j : factors)
				vals[t++] = j;
			for (int j = 0; j < arr.length; j++)
				arr[j] = (i - 1) / vals[j];
			for (int j = vals.length - 1; j >= 0; j--)
				for (int k = j + 1; k < vals.length; k++)
					if (vals[k] % vals[j] == 0)
						arr[j] -= arr[k];
			for (int j = 0; j < arr.length; j++)
				g[i] += arr[j] * vals[j];
		}
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		while (true) {
			String s = in.readLine();
			s = s.trim();
			int n = Integer.parseInt(s);
			if (n == 0)
				break;
			System.out.println(g[n]);

		}
	}
}

Posted February 8, 2012 by epicrado in Mathematics, Prime numbers

UVA – 10622 – Perfect P-th Powers   Leave a comment


import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.LinkedList;

public class PerfectPthPowers {
	public static int gcd(int a, int b) {
		return (b == 0) ? a : gcd(b, a % b);
	}

	public static void main(String[] args) throws Exception {
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		boolean[] isPrime = new boolean[1 << 16];
		isPrime[0] = isPrime[1] = true;
		for (int i = 2; i * i < isPrime.length; i++)
			if (!isPrime[i])
				for (int j = i * i; j < isPrime.length; j += i)
					isPrime[j] = true;
		LinkedList<Integer> res = new LinkedList<Integer>();
		for (int i = 2; i < isPrime.length; i++)
			if (!isPrime[i])
				res.add(i);
		while (true) {
			long t = Long.parseLong(in.readLine());
			if (t == 0)
				break;
			long sign = t / Math.abs(t);

			t = Math.abs(t);

			int g = 0;
			for (int i : res) {
				if (t % i == 0) {
					int c = 0;
					while (t % i == 0) {
						t /= i;
						c++;
					}
					g = gcd(c, g);
				}
				if (t == 1)
					break;
			}
			if (t != 1)
				g = gcd(1, g);
			while (sign < 0 && g % 2 == 0)
				g /= 2;
			System.out.println(g);
		}
	}
}

Posted February 6, 2012 by epicrado in GCD/LCM, Mathematics, Prime numbers

UVA – 11889 – Benefit   Leave a comment


import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
import java.util.TreeSet;

public class Benefit {
	public static void main(String[] args) throws NumberFormatException,
			IOException {
		int[] pfactor = new int[10000001];
		pfactor[0] = pfactor[1] = -1;
		for (int i = 2; i * i < pfactor.length; i++)
			if (pfactor[i] == 0)
				for (int j = i * i; j < pfactor.length; j += i)
					pfactor[j] = i;
		for (int i = 2; i < pfactor.length; i++)
			if (pfactor[i] == 0)
				pfactor[i] = i;
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		int t = Integer.parseInt(in.readLine());
		while (t-- > 0) {
			TreeSet<Integer> S = new TreeSet<Integer>();
			StringTokenizer st = new StringTokenizer(in.readLine(), " ");
			int a = Integer.parseInt(st.nextToken());
			int c = Integer.parseInt(st.nextToken());
			int temp = a;
			while (pfactor[temp] != -1) {
				S.add(pfactor[temp]);
				temp /= pfactor[temp];
			}
			boolean good = true;
			int res = c;
			for (int i : S) {
				int r1 = 1;
				int r2 = 1;
				int t1 = a;
				int t2 = c;
				while (t1 % i == 0) {
					t1 /= i;
					r1 *= i;
				}
				while (t2 % i == 0) {
					t2 /= i;
					r2 *= i;
				}
				if (r1 > r2) {
					good = false;
					break;
				}
				if (r1 == r2)
					res /= r1;
			}
			if (good)
				System.out.println(res);
			else
				System.out.println("NO SOLUTION");
		}
	}
}

Posted February 6, 2012 by epicrado in GCD/LCM, Mathematics, Prime numbers

UVA – 1246 – Find Terrorists   Leave a comment


In this problem we’re given two integers L and H and we are required to list all numbers between L and H (inclusive) which have a prime number of factors.
Let n be a number. then n can be written as p1^a * p2^b * p3^c….where a,b,c… are integers >= 0
we can easily prove that the number of factors of n is (a+1)*(b+1)*(c+1)….
and thus for a number to have a prime number of factors it must be either a Prime or a Power of a prime.
The solution is pretty direct we’ll generate all prime powers (p^a) such that a+1 is a prime number and store them.
We also must have a quick method to check weather a number is a prime or not here we used Miller-Rabin primality testing ( assuming L and H can reach 2^31 – 1 )
I believe this problem doesn’t require all this but the constrains weren’t given so i assumed they may be big.

import java.util.HashSet;
import java.util.LinkedList;
import java.util.Random;
import java.util.Scanner;

public class Terrorists {
	public static long modulo(long a, long b, long c) {
		long res = 1 % c;
		while (b != 0) {
			if ((b & 1) == 1)
				res = ((res % c) * (a % c)) % c;
			a = (a * a) % c;
			b >>= 1;
		}
		return res;
	}

	public static boolean isPrime(long p, int iter) {
		Random r = new Random();
		if (p < 2)
			return false;
		long q = p - 1;
		int k = 0;
		while (q % 2 == 0) {
			k++;
			q /= 2;
		}
		rand: for (int i = 0; i < iter; i++) {
			long a = Math.abs(r.nextLong()) % (p - 1) + 1;
			long mod = modulo(a, q, p);
			if (mod == 1 || mod == p - 1)
				continue;
			for (int j = 1; j < k; j++) {
				mod = (mod * mod) % p;
				if (mod == p - 1) {
					continue rand;
				}
			}
			return false;
		}
		return true;
	}

	public static void main(String[] args) {
		HashSet<Long> terr = new HashSet<Long>();
		boolean[] primes = new boolean[1 << 16];
		primes[0] = primes[1] = true;
		for (int i = 2; i * i < primes.length; i++)
			if (!primes[i])
				for (int j = i * i; j < primes.length; j += i)
					primes[j] = true;
		for (int i = 2; i < primes.length; i++)
			if (!primes[i]) {
				long res = (long) i * i;
				for (int j = 2; j < 32 && res < Integer.MAX_VALUE; j++, res *= i) {
					if (!primes[j + 1])
						terr.add(res);
				}
			}

		Scanner in = new Scanner(System.in);
		int n = in.nextInt();
		StringBuilder res = new StringBuilder();
		while (n-- > 0) {
			int l = in.nextInt();
			int h = in.nextInt();
			LinkedList<Integer> list = new LinkedList<Integer>();
			for (int i = l; i <= h; i++) {
				long k = i;
				if (terr.contains(k) || isPrime(k, 20)) {
					list.add(i);
				}
			}
			if (list.size() == 0)
				res.append("-1\n");
			else {
				int i = 0;
				for (int k : list) {
					res.append(k);
					i++;
					if (i < list.size())
						res.append(" ");
				}
				res.append("\n");
			}

		}
		System.out.print(res);
	}
}

Posted January 17, 2012 by epicrado in Prime numbers