class Solution {
public static ArrayList<Integer> primeFac(int n) {
ArrayList<Integer> ans = new ArrayList<>();
for(int i=2;i<=n;i++){
if(n%i == 0){
//ok i is a factor
if(isPrime(i)){
//ok i is a prime factor
[Link](i);
}
}
}
return ans;
}
private static boolean isPrime(int n){
if(n<2){
return false;
}
for(int i=2; i*i<=n; i++){
if(n%i == 0){
return false;
}
}
return true;
}
}
class Solution {
public static ArrayList<Integer> primeFac(int n) {
ArrayList<Integer> ans = new ArrayList<>();
for (int i=2; i*i<=n; i++) {
if (n % i == 0) {
// i is a factor
if (isPrime(i)) {
//i is a prime factor
[Link](i);
}
int other = n / i;
// Avoid duplicate if i == n / i
if (other != i && isPrime(other)) {
[Link](other);
}
}
}
//the number itself can as well, eg(7)
if (isPrime(n)) {
[Link](n);
}
return ans;
}
private static boolean isPrime(int n){
if(n<2){
return false;
}
for(int i=2; i*i<=n; i++){
if(n%i == 0){
return false;
}
}
return true;
}
}
class Solution {
public static ArrayList<Integer> primeFac(int n) {
ArrayList<Integer> ans = new ArrayList<>();
for (int i=2; i*i<=n; i++) {
if(!isPrime(i)){
continue;
}
if(n%i == 0){
[Link](i);
while(n%i == 0){
n = n/i;
}
}
}
if (n != 1) {
[Link](n);
}
return ans;
}
private static boolean isPrime(int n){
if(n<2){
return false;
}
for(int i=2; i*i<=n; i++){
if(n%i == 0){
return false;
}
}
return true;
}
}
class Solution {
public static void print_divisors(int n) {
ArrayList<Integer> firstHalf = new ArrayList<>();
ArrayList<Integer> secondHalf = new ArrayList<>();
for (int i = 1; i * i <= n; i++) {
if (n % i == 0) {
[Link](i);
if (i != n / i) {
[Link](n / i); // to be printed later in reverse
}
}
}
// Print in sorted order
for (int num : firstHalf) {
[Link](num + " ");
}
for (int i = [Link]() - 1; i >= 0; i--) {
[Link]([Link](i) + " ");
}
}
}
class Solution {
public int countPrimes(int n) {
// Create a boolean array to mark prime numbers from 0 to n
// By default, all are assumed to be prime (true)
boolean[] isPrime = new boolean[n + 1];
[Link](isPrime, true);
// Sieve of Eratosthenes: Mark non-primes
// Loop starts from 2 (smallest prime) up to sqrt(n)
for (int i = 2; i * i <= n; i++) {
// If 'i' is still marked as prime
if (isPrime[i]) {
// Mark all multiples of 'i' (i*i, i*i+i, i*i+2i, ...) as non-prime
for (int j = i * i; j <= n; j += i) {
isPrime[j] = false;
}
}
}
int count = 0;
// Count primes strictly less than n (i.e., in range [2, n-1])
for (int i = 2; i < n; i++) {
if (isPrime[i]) {
count++;
}
}
// Return the number of primes less than n
return count;
}
}
class Solution {
static int[] spf;
static final int MAXN = 200000; // Set this based on problem constraints
//sieve is called in the backend
static void sieve() {
spf = new int[MAXN + 1];
// Initialize: each number is its own smallest prime factor
for (int i = 0; i <= MAXN; i++) {
spf[i] = i;
}
// Sieve of Eratosthenes to find smallest prime factors
for (int i = 2; i * i <= MAXN; i++) {
if (spf[i] == i) { // i is prime
for (int j = i * i; j <= MAXN; j += i) {
if (spf[j] == j) {
spf[j] = i; // mark the smallest prime factor
}
}
}
}
}
// Factorizes N using the SPF array
static List<Integer> findPrimeFactors(int N) {
List<Integer> factors = new ArrayList<>();
while (N > 1) {
[Link](spf[N]);
N /= spf[N];
}
return factors;
}
}
class Solution {
public double myPow(double x, int n) {
if(n==0){
return 1;
}
if(n==1){
return x;
}
double val = 0;
if(n<0){
x = 1/x;
val = myPow(x,-(n/2));
}
else{
val = myPow(x,n/2);
}
if((n&1)==1){
//it is odd
return x * val * val;
}
else{
//it is even
return val * val;
}
}
}