Cheatography
https://cheatography.com
Sieve of Erath// Java program to print all primes smaller than or equal to
// n using Sieve of Eratosthenes
class SieveOfEratosthenes
{
void sieveOfEratosthenes(int n)
{
// Create a boolean array "prime[0..n]" and initialize
// all entries it as true. A value in prime[i] will
// finally be false if i is Not a prime, else true.
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] is not changed, then it is a prime
if(prime[p] == true)
{
// Update all multiples of p
for(int i = p*2; i <= n; i += p)
prime[i] = false;
}
}
// Print all prime numbers
for(int i = 2; i <= n; i++)
{
if(prime[i] == true)
System.out.print(i + " ");
}
}
|
3 Types of Decrease and ConquerDecrease by constant | Decrease by constant factor | variable-Size decrease | insertion sort | binary search and bisection method | Euclid's algoirthm | topolgical sorting | exponentiation by squaring | selection by partition | algorithms for generating permutations, subsets | multiplication a la russe | nim-like games |
| |
| | Brute-Force ProblemsProblem | Method | Complexity | TSP | Exhaustive | N! | KnapSack | Exhaustive | n*W |
Generate PermutationsExample n=3:
start: 1
12, 21
123, 132, 312
321, 231, 213
finish |
Euclidean AlgorithmExample:
GCD(270,192)
270/192 = 1 R 78
GCD(192, 78)
192/78 = 2 R 36
GCD(78,36)
78/36 = 2 R 6
GCD(36/6)
36/6 = 6 R0
since R = 0, 6 is GCD |
Brute Force Pros vs ConsPros | Cons | Wide applicability | Rarely Yields Efficient | Simple | Unacceptably Slow | Reasonable Algorithms | Not as constructive as others |
|
Help Us Go Positive!
We offset our carbon usage with Ecologi. Click the link below to help us!
Created By
Metadata
Favourited By
Comments
No comments yet. Add yours below!
Add a Comment
Related Cheat Sheets