|
Last updated on:
10 November 2008 06:01:30 PM
Topics in this section is sorted alphabetically
rather than in specific order. You may need to jump here to found what you
need. Since item numbering here doesn't reflect anything and since this
page will be expanded with more and more interesting mathematical facts,
I decide not to put item numbers.
Materials here usually don't need sophisticated
data structure or algorithm, but rather provides basic knowledge for subsequent
chapters.
Base
Number Conversion
Big Mod
Big Integer
Carmichael Number
Catalan Formula
Counting Combinations - C(N,K)
Divisors and Divisibility
Exponentiation
Factorial
Fibonacci
Greatest Common Divisor (GCD)
Lowest Common Multiple (LCM)
<math.h> - making the most of math library
Mathematical Expressions
Newton's Method
Prime Factors
Prime Numbers
Possible additions for this
page:
-. Making the most of C/C++ math library
-. Chinese Remainder Theorem
-. Fermat Theorem, etc...
Base Number Conversion
Decimal is
our most familiar base number, whereas computers are very familiar with
binary numbers (octal and hexa too). The ability to convert between bases
is important. Refer to mathematics book for this.
Big Mod
Modulo (remainder) is important arithmetic
operation and almost every programming language provide this basic operation.
However, basic modulo operation is not sufficient if we are interested in
finding a modulo of a very big integer, which will be difficult and has
tendency for overflow. Fortunately, we have a good formula here:
(A*B*C) mod
N == ((A mod N) * (B mod N) * (C mod N)) mod N.
To convince
you that this works, see the following example:
(7*11*23)
mod 5 is 1; let's see the calculations step by step:
((7 mod 5)
* (11 mod 5) * (23 mod 5)) Mod 5 =
((2 * 1 * 3) Mod 5) =
(6 Mod 5) = 1
Convinced? I hope you do.
If no, then please refer to some proof in the internet. For now, just assume
that this is true.
This formula is used
in several algorithm such as in Fermat Little Test for primality
testing:
R = B^P mod M (B^P is a very very big number). By using
the formula, we can get the correct answer without being afraid of overflow.
This is how to calculate R quickly
(using Divide & Conquer approach, see exponentiation below for more details):
long bigmod(long b,long p,long m) {
if (p == 0)
return 1;
else if (p%2 == 0)
return square(bigmod(b,p/2,m)) % m; // square(x) = x * x
else
return ((b % m) * bigmod(b,p-1,m)) % m;
}
Big Integer
Long time ago, 16-bit integer is sufficient:
[-2^15 .. 2^15-1] ~ [-32.768 .. 32.767].
When 32-bit machines are getting popular,
32-bit integers become necessary. This data type can hold range from
[-2^31 .. 2^31-1] ~ [2.147.483.648 .. 2.147.483.647]. Any integer with
9 or less digits can be safely computed using this data type. If you
somehow must use the 10th digit, be careful of overflow...
But man is very greedy, 64-bit integers
are created, referred as programmers as long long data type or Int64
data type. It has an awesome range up that can covers 18 digits integers
fully, plus the 19th digit partially [-2^63 .. 2^63-1] ~ [9.223.372.036.854.775.808
.. 9.223.372.036.854.775.807]. Practically this data type is safe to
compute most of standard arithmetic problems... except some problems...
Note: for those who don't know, in C,
long long n is read using: scanf("%lld",&n);
and unsigned long long n is read using: scanf("%llu",&n);
Now... RSA cryptography need 256 bits
of number or more... This is necessary, human always want more security
right? However, some problem setters in programming contests also follow
this trend... Simple problem such as finding n'th factorial will become
very very hard once the values exceed 64-bit integer data type... Yes,
long double can store very high numbers, but it actually only stores
first few digits and an exponent, long double is not precise.
In this case, you can't rely on standard
data type and need to implement your own arbitrary precision arithmetic
algorithm... Standard pen and pencil algorithm taught in elementary
school will be your tool to implement basic arithmetic operations: addition,
subtraction, multiplication and division. More sophisticated algorithm
are available to enhance the speed of multiplication and division...
Things are getting very complicated now...
Fortunately, there are several people
who have actually implement these Big Integer library and willing to
share the code with us. In Programming Challenges website, they offer
one version, but here, I want to share with you Big Integer library
by S. M. Mahbub Murshed Suman (udvranto
at yahoo.com).
Please click the following links to download
the library and a very
basic sample code. Follow the comments given in the sample code
to use the library.
The key feature of this library is its
ability to override C++ basic operations, making life easier for us,
programmers.
BigInteger n;
// try giving input: "1000000000000000000000000000000000000", this is
more than 19 digits
cin >> n;
cout << n << endl; // output will be: "1000000000000000000000000000000000000"
I've used this library to solve many UVa problems. Try it.
Carmichael Number
Carmichael number is a number which is
not prime but has >= 3 prime factors
You can compute them using prime number generator and prime factoring
algorithm.
The first 15 Carmichael numbers are:
561,1105,1729,2465,2821,6601,8911,10585,15841,29341,41041,46657,52633,62745,63973
Catalan Formula
The number of distinct binary trees can
be generalized as Catalan formula, denoted as C(n).
For details, please refer to [CLR chapter 13].
If you are asked values of several C(n),
it may be a good choice to compute the values bottom up. Since C(n+1)
can be expressed in C(n), as follows:
Catalan(n) =
2n!
---------------
n! * n! * (n+1)
Catalan(n+1) =
2*(n+1)
--------------------------- =
(n+1)! * (n+1)! * ((n+1)+1)
(2n+2) * (2n+1) * 2n!
------------------------------- =
(n+1) * n! * (n+1) * n! * (n+2)
(2n+2) * (2n+1) * 2n!
----------------------------------- =
(n+1) * (n+2) * n! * n! * (n+1)
(2n+2) * (2n+1)
--------------- * Catalan(n)
(n+1) * (n+2)
Counting Combinations - C(N,K)
C(N,K) means how many ways that N things can
be taken K at a time.
This can be a great challenge when N and/or K become very large.
Combination of (N,K) is defined as:
N!
----------
(N-K)!*K!
For your information, the exact value of 100!
is:
93,326,215,443,944,152,681,699,238,856,266,700,490,715,968,264,381,621,
468,592,963,895,217,599,993,229,915,608,941,463,976,156,518,286,253,
697,920,827,223,758,251,185,210,916,864,000,000,000,000,000,000,000,000
so, how to compute the values of C(N,K) when
N and/or K is big but the result is guaranteed to fit in 32-bit integer?
1. "Underflow" computation + Real number (sample
code in Pascal)
var n,k,i:longint;
R:real;
begin
readln(n,k);
R:=1;
if (k>n-k) then k:=n-k; { use smaller k!!!, note C(10,6)==C(10,4) }
for i:=1 to k do R:=R/i; { "underflow" multiplication }
for i:=n downto n-k+1 do R:=R*i;
writeln(round(R));
end.
2. Divide by GCD before multiply (sample code
in C)
long gcd(long a,long b) {
if (a%b==0) return b; else return gcd(b,a%b);
}
void Divbygcd(long& a,long& b) {
long g=gcd(a,b);
a/=g;
b/=g;
}
long C(int n,int k){
long numerator=1,denominator=1,toMul,toDiv,i;
if (k>n/2) k=n-k; /* use smaller k */
for (i=k;i;i--) {
toMul=n-k+i;
toDiv=i;
Divbygcd(toMul,toDiv); /*
always divide before multiply */
Divbygcd(numerator,toDiv);
Divbygcd(toMul,denominator);
numerator*=toMul;
denominator*=toDiv;
}
return numerator/denominator;
}
Divisors and Divisibility
If d is
a divisor of n, then so is n/d, but d & n/d cannot both be greater than
sqrt(n).
Example:
2 is a
divisor of 6, so 6/2 = 3 is also a divisor of 6
(Simple isn't it, but it is very useful)
Let N
= 25, Therefore no divisor will be greater than sqrt (25) = 5.
(Divisors of 25 is 1 & 5 only)
If you keep
that rule in your mind, you can design an algorithm to find a divisor better,
that's it, no divisor of a number can be greater than the square root of
that particular number.
If a number N == a^i * b^j * ... * c^k then N has (i+1)*(j+1)*...*(k+1)
divisors.
Example:
N = 60
60 = 2^2 * 3^1 * 5^1
Therefore 60 has (2+1)*(1+1)*(1+1) = 3*2*2=12 divisors
The divisors are: 1,2,3,4,5,6,10,12,15,20,30,60
There are
many more interesting divisibility properties, these were found by mathematics
people, who spent their time researching these properties... When I know
more, I'll post it here.
|
TEST YOUR DIVISIBILITY KNOWLEDGE
Solve UVa
problems related with Divisibility:
294 - Divisors
|
Exponentiation
(Assume
pow() function in <math.h> doesn't exist...). Sometimes we want to do exponentiation
or take a number to the power n. There are many ways to do that. The standard
method is standard multiplication.
Standard multiplication
long exponent(long base,long power) {
long i,result = 1;
for (i=0; i<power; i++) result *= base;
return result;
}
This is 'slow',
especially when power is big - O(n) time. It's better to use divide & conquer.
Divide & Conquer
exponentiation
You can express a^n in 2 ways:
a^n = (a^(n/2))^2 if n is even, or
a^n = a*a^(n-1) if n is odd
Example:
Normal:
2*2*2*2*2*2*2*2 ~~ 8 multiplications ~~ O(n).
Divide & Conquer:
2^8 == (a^4)^2 == ((a^2)^2)^2 ~~ 3 multiplications ~~ O(log n).
Remember that
O(log n) is much faster than O(n).
long square(long n) { return n*n; }
long fastexp(long base,long power) {
if (power == 0)
return 1;
else if (power%2 == 0)
return square(fastexp(base,power/2));
else
return base * (fastexp(base,power-1));
}
Using built in formula, a^n = exp(log(a)*n)
or pow(a,n)
#include <stdio.h>
#include <math.h>
void main() {
printf("%lf\n",exp(log(8.0)*1/3.0));
printf("%lf\n",pow(8.0,1/3.0));
}
Both method
produce the same answer. Fortunately, many compilers provide this exponent,
natural logarithm, or power function in their math library. More interestingly,
these mathematical formula is capable of handling fractions, as shown above:
8^(1/3) = cubicroot(8) =
2
This cannot be done using standard a^n = a*a*a..*a (n times)...
If you need
integer result, just round the result, simple.
Factorial
Factorial
is naturally defined as Fac(n) = n * Fac(n-1).
This is a
recursive function. Fac function will always called itself until the
base case. The base case for factorial is when n == 0. By mathematical
definition, factorial of 0 is 1.
Example:
Fac(3) = 3
* Fac(2)
Fac(3) = 3 * 2 * Fac(1)
Fac(3) = 3 * 2 * 1 * Fac(0)
Fac(3) = 3 * 2 * 1 * 1
Fac(3) = 6
As you see,
this leads into a series of postponed operations. Always try to avoid recursive
function unless it's the only way to solve a problem. In this example, factorial
can be written as iterative function, so use the iterative version instead.
Iterative
version of factorial
long FacIter(int
n) {
int i,result = 1;
for (i=2; i<=n; i++) result *= i; // index 'i' starts from 2 until n
as 'result' starts from 1.
return result;
}
So far, I reckon that this
is the best algorithm to compute factorial... O(n).
Fibonacci
Fibonacci
numbers was invented by Leonardo of Pisa (Fibonacci). He defined fibonacci
numbers as a growing population of immortal rabbits. Series of Fibonacci
numbers are: 1,1,2,3,5,8,13,21,...
To compute
Fibonacci numbers directly, you can simply compute the closest integer of
Ø^n / sqrt(5) where Ø (golden ratio) is ((1+sqrt(5))/2) ~~ 1.618. However
this is not so accurate for big numbers.
Recurrence
relation for Fib(n):
Fib(0) = 0
Fib(1) = 1
Fib(n) = Fib(n-1) + Fib(n-2)
If you implement
Fibonacci using this method, you will create a tree recursion, it has an
exponential growth and too slow.
Iterative
version of Fibonacci (using Dynamic Programming)
int fib(int n) {
int a=1,b=1,i,c;
for (i=3; i<=n; i++) {
c = a+b;
a = b;
b = c;
}
return a;
}
This algorithm runs in linear time O(n).
Quick method to
quickly compute Fibonacci, using Matrix property.
_
_ n _
_
| 0 1 | = | fn-2
fn-1 |
|_ 1 1 _| |_ fn-1
fn _|
I don't really understand the derivation,
but this is the O(log n) code:
Divide_Conquer_Fib(n) {
i = h = 1;
j = k = 0;
while (n > 0) {
if (n%2 == 1) { // if n is odd
t = j*h;
j = i*h + j*k + t;
i = i*k + t;
}
t = h*h;
h = 2*k*h + t;
k = k*k + t;
n = (int) n/2;
}
return j;
}
This runs in O(log n) time.
Greatest Common Divisor (GCD)
As it name
suggest, Greatest Common Divisor (GCD) algorithm finds the greatest common
divisor between two number a and b. GCD is a very useful technique, for
example to reduce rational numbers into its smallest version (3/6 = 1/2).
The best GCD
algorithm so far is Euclid's Algorithm.
Euclid
found this interesting mathematical equality. GCD(a,b) = GCD (b,(a mod b)).
This algorithm
is very effective and it's order of growth is an efficient O(log n).
Example: Compute
GCD of 40 and 6
GCD(40,6)
= GCD(6,4) = GCD(4, 2) = GCD(2,0) -> stop here, because one of the arguments
is zero, the other argument that is not zero is the GCD.
Here is the fastest implementation of GCD
algorithm (use int data type to make it faster if you know that you'll not
using big numbers), using only 2 variables (see Swapping 2 values section)
and change recursion into iteration.
int GCD(int a,int b) {
while (b > 0) {
a = a % b;
a ^= b;
b ^= a;
a ^= b;
}
return a;
}
Later: Extended Euclid... (soon)
Lowest Common Multiple (LCM)
Lowest Common
Multiple and Greatest Common Divisor (GCD) are two important number properties,
and they are interrelated. Even though GCD is more often used than LCM,
it is useful to learn LCM too.
LCM (m,n)
= (m * n) / GCD (m,n)
Example:
LCM (3,2)
= (3 * 2) / GCD (3,2)
LCM (3,2) = 6 / 1
LCM (3,2) = 6
Application
of LCM -> to find a synchronization time between two traffic light, if traffic
light A display green color every 3 minutes and traffic light B display
green color every 2 minutes, then every 6 minutes, both traffic light will
display green color at the same time.
Mathematical Expressions
There are
three types of mathematical/algebraic expressions. They are Infix, Prefix,
& Postfix expressions.
Infix
expression grammar:
<infix> = <identifier> | <infix><operator><infix>
<operator> = + | - | * | /
<identifier> = a | b | .... | z
Infix expression
example: (1 + 2) => 3, the operator is in the middle of two operands.
Infix expression is the normal way human compute numbers.
Prefix
expression grammar:
<prefix> = <identifier> | <operator><prefix><prefix>
<operator> = + | - | * | /
<identifier> = a | b | .... | z
Prefix expression
example: (+ 1 2) => (1 + 2) = 3, the operator is the first item.
One programming language that use this expression is Scheme language.
The benefit of prefix expression is it allows you write: (1 + 2 + 3 + 4)
like this (+ 1 2 3 4), this is simpler.
Postfix
expression grammar:
<postfix> = <identifier> | <postfix><postfix><operator>
<operator> = + | - | * | /
<identifier> = a | b | .... | z
Postfix expression
example: (1 2 +) => (1 + 2) = 3, the operator is the last item.
Postfix Calculator
Computer do
postfix calculation better than infix calculation. Therefore when you compile
your program, the compiler will convert your infix expressions (most programming
language use infix) into postfix, the computer-friendly version.
Why do computer
like Postfix better than Infix?
It's because
computer use stack data structure, and postfix calculation can be done easily
using stack.
Postfix calculation
algorithm => Link to this file will be available later.
Infix to Postfix conversion
To use this very efficient Postfix calculation,
we need to convert our Infix expression into Postfix. This is how we do
it:
Example:
Infix statement: ( ( 4 - ( 1 + 2 * ( 6 / 3
) - 5 ) ) )
This is what the algorithm will do, look carefully
at the steps. Red colour is the character being
analyzed.
|
Expression
|
Stack (bottom to top)
|
Postfix expression
|
|
((4-(1+2*(6/3)-5)))
|
(
|
|
|
((4-(1+2*(6/3)-5)))
|
((
|
|
|
((4-(1+2*(6/3)-5)))
|
((
|
4
|
|
((4-(1+2*(6/3)-5)))
|
((-
|
4
|
|
((4-(1+2*(6/3)-5)))
|
((-(
|
4
|
|
((4-(1+2*(6/3)-5)))
|
((-(
|
41
|
|
((4-(1+2*(6/3)-5)))
|
((-(+
|
41
|
|
((4-(1+2*(6/3)-5)))
|
((-(+
|
412
|
|
((4-(1+2*(6/3)-5)))
|
((-(+*
|
412
|
|
((4-(1+2*(6/3)-5)))
|
((-(+*(
|
412
|
|
((4-(1+2*(6/3)-5)))
|
((-(+*(
|
4126
|
|
((4-(1+2*(6/3)-5)))
|
((-(+*(/
|
4126
|
|
((4-(1+2*(6/3)-5)))
|
((-(+*(/
|
41263
|
|
((4-(1+2*(6/3)-5)))
|
((-(+*
|
41263/
|
|
((4-(1+2*(6/3)-5)))
|
((-(-
|
41263/*+
|
|
((4-(1+2*(6/3)-5)))
|
((-(-
|
41263/*+5
|
|
((4-(1+2*(6/3)-5)))
|
((-
|
41263/*+5-
|
|
((4-(1+2*(6/3)-5)))
|
(
|
41263/*+5--
|
|
((4-(1+2*(6/3)-5)))
|
|
41263/*+5--
|
|
TEST YOUR INFIX->POSTFIX KNOWLEDGE
Solve UVa
problems related with postfix conversion:
727 - Equation
|
Newton's Method
Square roots
How computer calculate roots?, here is one
of the method:
|
Guess
|
Quotient
|
Average
|
|
1
|
2/1
|
2
|
(2+1)/2
|
1.5
|
|
1.5
|
2/1.5
|
1.3333
|
(1.5+1.333)/2
|
1.4167
|
|
1.4167
|
2/1.4167
|
14118
|
(1.4167+1.4118)/2
|
1.4142
|
|
1.4142
|
...
|
...
|
...
|
...
|
We are using
approximation in determining the square root of a given number X (in this
case = 2), we start the guess with 1, then repeat the process until we get
Y that is good enough (ie Y*Y - X = 0.001, if 0.001 is the precision that
we want). Of course, better precision means more time to compute.
Cubic roots
How about cubic roots? Similar...
|
Guess
|
Y Value
|
New Y
|
|
1
|
(4/(1^2) + 2*1)/3
|
2
|
|
2
|
(4/(2^2) + 2*2)/3
|
1.6666
|
|
1.6666
|
(4/(1.6666^2) + 2*1.6666)/3
|
1.5911
|
|
1.5911
|
...
|
...
|
If Y is an
approximation to the cube root of X, then the cube roots of X is given by
the formula: (X/(Y^2) + 2*Y)/3. In above example, X = 8, and initial guess
(Y) is 1.
Note that these methods are
not precise...
Prime Factors
Definition:
All integers can be expressed as a product of primes and these primes are
called prime factors of that number.
Exceptions
(My opinion):
For negative integers, multiply by -1 to make it positive again.
For -1,0, and 1, no prime factor... (by definition...)
Standard way
Generate a
prime list again, and then check how many of those primes can divide n.
This is very
slow. Maybe you can write a very efficient code using this algorithm, but
there is another algorithm that is much more effective than this.
Restatement
of Standard way
Check the
factors first, and then test whether the factor is a prime or not.
This is one
is slightly faster than standard way... sometimes restatement of an algorithm
(viewing an algorithm from different side) can make it very different.
Creative way,
using Number Theory
-
Don't
generate prime, or even checking for primality :-)
-
Always
use stop-at-sqrt technique
-
Remember
to check repetitive prime factors, example=20->2*2*5, don't count 2
twice. We want distinct primes (however, several problems actually require
you to count these multiples..., so, please be careful)
-
Make your
program use constant memory space, no array needed.
-
Use the
definition of prime factors wisely, this is the key idea. A number can
always be divided into a prime factor and another prime factor or another
number. This is called the factorization tree.
Example:
N
\
100
/ \
2 50
/ \
2 25
/ \
5 5
/ \
5
1
From this
factorization tree, we can determine these following properties:
-
If we
take out a prime factor (F) from any number N, then the N will become
smaller and smaller until it become 1, we stop here.
-
This smaller
N can be a prime factor or it can be another smaller number, we don't
care, all we have to do is to repeat this process until N=1.
Further optimization
is we can assume the factors are all odd (No even primes except for 2),
second optimization is to stop when current factor is > sqrt (N). Here,
we have to determine whether N has reached 1 or not, if N != 1, then N is
prime too, then we have to add one more to our total prime factors.
|
TEST YOUR PRIME FACTORS KNOWLEDGE
Solve UVa
problems related with prime factors:
583 - Prime Factors
|
Prime Numbers
Prime numbers
are important in Computer Science (For example: Cryptography) and finding
prime numbers in a given interval is a "tedious" task (for your computer,
not for you :-). Usually, we are looking for big (very big) prime numbers
therefore searching for a better prime numbers algorithms will never stop.
Many algorithms
were created to find this prime numbers, each has different style, one is
fast to code but slow when running, the other is difficult to code but can
run in reasonable time.
However, the
easiest method to find whether a given number is a prime or not is by testing
it divisibility. If it can only be divided by 1 or by itself then it's prime.
Of course, use efficient method!!!
Standard Divisibility
Check / Trial Division (improved version):
This optimization
trick was taken from USACO problem explanation for Super Prime Rib
Use optimized trial division for standard prime testing only. This algorithm
is not fast enough for bigger number!!!
1. Standard prime testing
int
is_prime(int n) {
for (int i=2; i<=(int) sqrt(n); i++) if (n%i == 0) return 0;
return 1;
}
This is
extremely slow. A test that did no more than check the first 10,000
integers for primality ran for about 10.7 seconds on P90 machine. Here's
the tester program:
void
main() {
int i,count=0;
for (i=1; i<10000; i++) count += is_prime(i);
printf("Total of %d primes\n",count);
}
2. Pull out the sqrt call
The first
optimization was to pull the sqrt call out of the limit test, just in
case the compiler wasn't optimizing that correctly, this one is faster:
int
is_prime(int n) {
long lim = (int) sqrt(n);
for (int i=2; i<=lim; i++) if (n%i == 0) return 0;
return 1;
}
3. Restatement of sqrt.
But you
know what? You don't need to do that. You can just check to ensure i*i<n
instead of i<sqrt(n). No significant execution time decrease, though.
However, no floating point operations is usually a big win:
int
is_prime(int n) {
for (int i=2; i*i<=n; i++) if (n%i == 0) return 0;
return 1;
}
4. We don't need to check even numbers
If you
think about it, there's really no reason to try all those even numbers
and check the divisibility property by jumping 2 numbers starting from
3 (That's it, check odd numbers only). You could do something like this
and get another 20x speed improvement!!! It's pretty quick:
int
is_prime(int n) {
if (n == 1) return 0; //
1 is NOT a prime
if (n == 2) return 1; //
2 is a prime
if (n%2 == 0) return 0; // NO prime is
EVEN, except 2
for (int i=3; i*i<=n; i+=2) // start from 3, jump 2 numbers
if (n%i == 0)
// no need to check even numbers
return 0;
return 1;
}
5. Other prime properties
A (very)
little bit of thought should tell you that no prime can end in 0,2,4,5,6,
or 8, leaving only 1,3,7, and 9.
It's fast
& easy. Memorize this technique. It'll be very helpful for your programming
assignments dealing with relatively small prime numbers (16-bit integer
1-32767). This divisibility check (step 1 to 5) will not be suitable
for bigger numbers.
6. Divisibility
check using smaller primes below sqrt(N):
Actually,
we can improve divisibility check for bigger numbers. Further investigation
concludes that a number N is a prime if and only if no primes below
sqrt(N) can divide N.
Since
this algorithm needs to know previous smaller primes, then this algorithm
is more suitable for prime numbers generator, not prime tester.
How to
do this:
-
Create
a large array. How large? here is the explanation
-
Suppose
max primes generated will not greater than 2^31-1 (2.147.483.647),
maximum 32-bit integer.
-
Since
you need smaller primes below sqrt(N), you only need to store primes
from 1 to sqrt(2^31)
-
Quick
calculation will show that of sqrt(2^31) = 46340.95.
-
After
some calculation, you'll find out that there will be at most 4792
primes in the range 1 to 46340.95. So you only need about array
of size (roughly) 4800 elements.
-
Generate
that prime numbers from 1 to 46340.955. This will take time, but
when you already have those 4792 primes in hand, you'll be able
to use those values to determine whether a bigger number is a prime
or not.
-
Now
you have 4792 first primes in hand. All you have to do next is to
check whether a big number N a prime or not by dividing it with
small primes up to sqrt(N). If you can find at least one small primes
can divide N, then N is not prime, otherwise N is prime.
Fermat Little
Test:
This is a
probabilistic algorithm so you cannot guarantee the possibility of getting
correct answer. In a range as big as 1-1000000, Fermat Little Test can be
fooled by (only) 255 Carmichael numbers (numbers that can fool Fermat Little
Test, see Carmichael numbers above). However, you can do multiple random
checks to increase this probability.
Fermat Algorithm
(don't ask me why, I don't know why this formula is like this):
If 2^N
modulo N = 2 then N has a high probability to be a prime number.
Example:
let N=3 (we know that 3 is a prime).
2^3 mod 3 = 8 mod 3 = 2, then N has a high probability to be a prime number...
and in fact, it is really prime.
Another example:
let N=11 (we know that 11 is a prime).
2^11 mod 11 = 2048 mod 11 = 2, then N has a high probability to be a prime
number... again, this is also really prime.
This algorithm
will be fast if you know how to do big exponentiation and modulo (again,
use the big mod algorithm specified in this page). When N > 31, 2^N will
exceed 2^31 (Maximum of 32-bit integer). However, this is not so easy, and
according to my experience, bigger numbers tends to make Fermat Little Test
produce a wrong answer. I myself don't really like this algorithm for
programming contests since it's reliability is not guaranteed. You'll
likely get Wrong Answer...
Sieve of Eratosthenes:
Sieve is the
best prime generator algorithm. It will generate a list of primes very quickly,
but it will need a very big memory. You can use Boolean flags to do this
(Boolean is only 1 byte).
This is what
Eratosthenes (from Greece) did thousand years ago:
He start with
a list of numbers, excluding one because one is not a prime
2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20...
He preserve
number 2 (red),
but deletes all numbers that are multiples of 2 (blue).
2
3 4
5 6
7 8
9
10
11 12
13 14
15 16
17 18
19 20...
He continue
to the next undeleted number 3 (red),
but deletes all numbers that are multiples of 3 (blue),
if it already deleted by previous checks (multiples of 2), he simply ignores
it.
2
3
4
5 6
7 8
9
10
11 12
13 14
15
16
17 18
19 20...
He continue
to the next undeleted number 5 (red),
but deletes all numbers that are multiples of 5 (blue),
if it already deleted by previous checks (multiples of 3), he simply ignores
it.
2
3
4
5
6
7 8
9
10
11 12
13 14
15
16
17 18
19 20...
He do
it again and again...until all has been marked.
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20...
This will be very fast, because
you didn't do any division, multiplication, or modulo/remainder and
you only need to strike out numbers from 2 till sqrt(N) because after that,
all the non primes will have been deleted out by the multiples of previous
values.
Algorithm for Sieve of Eratosthenes
to find the prime numbers within a
range L,U (inclusive), where must be L<=U.
void sieve(int L,int U) {
int i,j,d;
d=U-L+1; /* from range L to U, we have d=U-L+1 numbers. */
/* use flag[i] to mark whether (L+i) is a prime number or not. */
bool *flag=new bool[d];
for (i=0;i<d;i++) flag[i]=true; /* default: mark all to be true */
for (i=(L%2!=0);i<d;i+=2) flag[i]=false; /* mark even numbers as false */
/* sieve by prime factors staring from 3 till sqrt(U) */
for (i=3;i<=sqrt(U);i+=2) {
if (i>L && !flag[i-L]) continue;
/* choose the first number to be sieved -- >=L,
divisible by i, and not i itself! */
j=L/i*i;
if (j<L) j+=i;
if (j==i) j+=i; /* if j is a prime number, have to start form
next one */
/* now start sieving */
j-=L; /* change j to the index representing j */
for (;j<d;j+=i) flag[j]=false;
}
/* mark 1 as false, 2 as true */
if (L<=1) flag[1-L]=false;
if (L<=2) flag[2-L]=true;
/* output the result */
for (i=0;i<d;i++) if (flag[i]) cout << (L+i) << " ";
cout << endl;
}
Solution from Zhang Kaicheng
Popular Prime
Numbers:
First prime and the only even
prime: 2
Perfect prime: 7 (because I like 7 :-P)
In the range 1 to 100 : 25 primes
In the range 1 to 1000 : 168 primes
In the range 1 to 7919 : 1000 primes
In the range 1 to 10000 : 1229 primes
Largest prime in 32-bit integer range: 2^31 - 1 = 2.147.483.647
Funny stuff
about Prime Numbers :-)
A "Theorem": All odd numbers
is a prime
Taken from Prof Leong Hong Wai joke during CS1305 lecture.
Mathematician:
3 prime, 5 prime, 7 prime, 9 not prime... aha!!! Therefore this theorem
is false.
Physicist:
3 prime, 5 prime, 7 prime, 9 OOPS experimental error, ignore this, 11 prime,
13 prime, this theorem is true
Engineer:
3 prime, 5 prime, 7 prime, 9 prime, 11 prime, 13 prime, hmm.. nothing wrong
here, this theorem is true.
Computer Scientist:
3 prime, 5 prime, 7 prime, 7 prime, 7 prime, 7 prime, 7 prime, 7 prime (Infinite
loop :-).
What's Next?
After reading this page, you should be able
to handle many mathematical-related problems. There are much more harder
mathematical-related problems that I can't solve, due to my poor math...
However, I hope this page can give you something new to be learnt. Next,
we are going to study two basic techniques in CS, Sorting and Searching.
Stay tuned :D.
This document, 4_mathematics.html, has been accessed 19412 times since 02-Aug-04 14:13:06 SGT.
This is the 12th time it has been accessed today.
A total of 10880 different hosts have accessed this document in the
last 1584 days; your host, 38.103.63.56, has accessed it 1 times.
If you're interested, complete statistics for
this document are also available, including breakdowns by top-level
domain, host name, and date.
|
