Scribd
Upload
1 views5 pages

Cp algo

The document contains Java code snippets for three main algorithms: a Sieve of Eratosthenes implementation to find prime numbers, a prime factorization method, and a check for whether a number is a power of two using bitwise operators. It also includes notes on GCD properties and calculations. Each section is structured with a main method that takes user input to execute the respective algorithm.

Uploaded by

mdwivedigod
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
1 views5 pages

Cp algo

The document contains Java code snippets for three main algorithms: a Sieve of Eratosthenes implementation to find prime numbers, a prime factorization method, and a check for whether a number is a power of two using bitwise operators. It also includes notes on GCD properties and calculations. Each section is structured with a main method that takes user input to execute the respective algorithm.

Uploaded by

mdwivedigod
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
You are on page 1/ 5

1.

SEIVE-
public static void sieve(int n) {

boolean[] isPrime = new boolean[n + 1];

Arrays.fill(isPrime, true); // Assume all numbers are prime initially

isPrime[0] = isPrime[1] = false; // 0 and 1 are not prime

for (int i = 2; i * i <= n; i++) {

if (isPrime[i]) { // If i is prime

for (int j = i * i; j <= n; j += i) {

isPrime[j] = false; // Mark multiples of i as non-prime

// Print all prime numbers

System.out.println("Prime numbers up to " + n + ":");

for (int i = 2; i <= n; i++) {

if (isPrime[i]) {

System.out.print(i + " ");

System.out.println();

public static void main(String[] args) {

Scanner scanner = new Scanner(System.in);

System.out.print("Enter the value of N: ");

int n = scanner.nextInt();
sieve(n);

scanner.close();

2. PRIME FACTORIZATION
3. import java.util.*;
4. public class Main{
5. static void primefactorization(int n)
6. {
7. for(int i=2;i*i<n;i++)
8. {
9. if(n%i==0)
10. {
11. int cnt=0;
12. while(n%i==0)
13. {
14. cnt++;
15. n/=i;
16. }
17. System.out.print(i+"^"+cnt+" ");
18. }
19. }
20. System.out.println();
21. if(n>1) System.out.println(n+"^"+"1");
22. }
23. public static void main(String[] args)
24. {
25. Scanner in=new Scanner(System.in);
26. int n=in.nextInt();
27. primefactorization(n);
28. in.close();
29.
30. }
31. }

USE OF BITWISE OPERATOR FOR CHECKING IF


A NUMBER IS A POWER OF 2;
import java.util.*;

public class PowerOfTwoCheck {


public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int t = in.nextInt(); // Number of test cases
while (t-- > 0) {
long n = in.nextLong();
if ((n & (n - 1)) != 0) {

// IF THIS HOLDS THEN NUMBER IS NOT A POWER OF 2

System.out.println("YES");
} else {
System.out.println("NO");
}
}
in.close();
}
}

BITMASK AND BITWISE


AND-https://en.wikipedia.org/wiki/Bitwise_op
eration#AND

CALCULATING CEIL- (FOR LARGE VALUES OF N)


// add (n-1) in numerator
GCD-(Greatest Common Factor)
GCD(a, b) = GCD(b, a % b)
Key Rule:
 Adding same number to both numbers: GCD
may change
 Subtracting same number from one of them
(or using mod): GCD stays same

You might also like