Maths Flashcards
What is the the trial division method to find number is prime or not?
To find number is prime or not , we need to divide all the numbers less than number till 2. If it is divisible by any number(number%(n-1)==0) then its not prime number.
Trial division method divide number by all numbers less than or equal to sqrt of number rather than dividing by all the numbers
What is the most efficient way of finding prime numbers smaller than n(where n is smaller then one million or so)?
Sieve of Eratosthenes
Time complexity of Sieve of Eratosthenes?
https://www.youtube.com/watch?v=eKp56OLhoQs
O(nloglogn)
Pseudo code for Sieve of Eratosthenes?
https://www.cs.cmu.edu/~scandal/cacm/node8.html procedure PRIME(n): let A be an array of length n set all elements of A to true for i from 2 to √n begin ifA[i] is True then set all the multiples of i up to n to FALSE end
Euclid’s algorithm for finding GCD?
public int GCD(int a, int b)
{
if (b == 0)
return a;
return GCD(b, a % b); }
Formula for sum of integers from 1 to n
n*(n+1)/2
Power function for calculating recursively
power(x, y / 2) * power(x, y / 2) for even
x * power(x, y / 2) * power(x, y / 2); for odd
How to calculate common difference between the successive elements of the sequence
https://www.techiedelight.com/find-missing-term-sequence-ologn-time/
(last element in sequence -first element in sequence)/total elements in sequence
Formula for next sequence element in array
a[i]=d*i + a[0]
where i is ith element or the index in array
and d is the common difference
0 1 2 3 4 5
5 7 9 11 13 15
a[5]=2*5 + 5
Total number of combinations for n items are?
2^n
How to find LCM of two given numbers?
https://www.youtube.com/watch?v=8E1i5l6h22c
(GCDLCM)=(ab)
LCM=(a*b)/(GCD)
How to find the number of digits in number?
(int)Math.Floor(Math.Log10(n) + 1);
Formula for quickly incrementing/decrementing digit by 1 ,assuming that digits are in range 0 to 9?
(10+n+1)%10 where n is in range 0 to 9
(10+n-1)%10 where n is in range 0 to 9
How to calculate the remainder for the negative number n when taking mod with negative number?
((n%K)+K)%K
Given a string s=’123’ , how to convert it into number without using build-in function?
int number = 0; while (char.IsNumber(s[index])) { number = 10 * number + (s[index] - '0'); \++index; } return number;