Movatterモバイル変換

[0]ホーム
URL:

Skip to content

Navigation Menu

Sign in
Appearance settings

Search code, repositories, users, issues, pull requests...

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly

 Sign up
Appearance settings

Commit30ef6a3

Browse files
committed
Add prime factors calculation.
1 parent827906c commit30ef6a3

File tree

6 files changed

+147
-102
lines changed

6 files changed

+147
-102
lines changed

‎README.md

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -66,7 +66,7 @@ a set of rules that precisely define a sequence of operations.
6666
*`B`[Bit Manipulation](src/algorithms/math/bits) - set/get/update/clear bits, multiplication/division by two, make negative etc.
6767
*`B`[Factorial](src/algorithms/math/factorial)
6868
*`B`[Fibonacci Number](src/algorithms/math/fibonacci) - classic and closed-form versions
69-
*`B`[Prime Factors](src/algorithms/math/prime-factors) - findingdistinctprime-factor count using both accurate & Hardy-Ramanujan'sAlgorithm
69+
*`B`[Prime Factors](src/algorithms/math/prime-factors) - finding prime factors and counting them using Hardy-Ramanujan'stheorem
7070
*`B`[Primality Test](src/algorithms/math/primality-test) (trial division method)
7171
*`B`[Euclidean Algorithm](src/algorithms/math/euclidean-algorithm) - calculate the Greatest Common Divisor (GCD)
7272
*`B`[Least Common Multiple](src/algorithms/math/least-common-multiple) (LCM)
Lines changed: 17 additions & 17 deletions
Original file line numberDiff line numberDiff line change
@@ -1,34 +1,34 @@
11
#Prime Factors
22

3-
Primefactors are basically those prime numbers which multiply together to give the orignalnumber. For ex: 39 will have prime factors as 3 and 13 which are alsoprime numbers. Another example is 15 whose prime factors are 3 and5.
3+
**Primenumber** is a wholenumber greater than`1` that**cannot** be made by multiplying other whole numbers. The first fewprime numbers are:`2`,`3`,`5`,`7`,`11`,`13`,`17`,`19` andso on.
44

5-
####Method for finding the prime factors and their count accurately
5+
If we**can** make it by multiplying other whole numbers it is a**Composite Number**.
66

7-
The approach is to basically keep on dividing the natural number 'n' by indexes from i = 2 to i = n by prime indexes only. This is ensured by an 'if' check. Then value of 'n' keeps on overriding by (n/i).
8-
The time complexity till now is O(n) in worst case since the loop run from index i = 2 to i = n even when no index 'i' is left to be divided by 'n' other than n itself. This time complexity can be reduced to O(sqrt(n)) from O(n). This optimisation is acheivable when loop is ran from i = 2 to i = sqrt(n). Now, we go only till O(sqrt(n)) because when 'i' becomes greater than sqrt(n), we now have the confirmation there is no index 'i' left which can divide 'n' completely other than n itself.
7+
![Composite numbers](https://www.mathsisfun.com/numbers/images/prime-composite.svg)
98

10-
#####Optimised Time Complexity: O(sqrt(n))
9+
_Image source:[Math is Fun](https://www.mathsisfun.com/prime-factorization.html)_
1110

11+
**Prime factors** are those[prime numbers](https://en.wikipedia.org/wiki/Prime_number) which multiply together to give the original number. For example`39` will have prime factors of`3` and`13` which are also prime numbers. Another example is`15` whose prime factors are`3` and`5`.
1212

13-
####Hardy-Ramanujan formula for approximate calculation of prime-factor count
13+
![Factors](https://www.mathsisfun.com/numbers/images/factor-2x3.svg)
1414

15-
In 1917, a theorem was formulated by G.H Hardy and Srinivasa Ramanujan which approximately tells the total count of distinct prime factors of most 'n' natural numbers.
16-
The fomula is given by ln(ln(n)).
15+
_Image source:[Math is Fun](https://www.mathsisfun.com/prime-factorization.html)_
1716

18-
####Code Explaiation
17+
##Finding the prime factors and their count accurately
1918

20-
There areon4 functions used:
19+
The approach is to keepondividing the natural number`n` by indexes from`i = 2` to`i = n` (by prime indexes only). The value of`n` is being overridden by`(n / i)` on each iteration.
2120

22-
- getPrimeFactors : returns array containing all distinct prime factors for given input n.
21+
The time complexity till now is`O(n)` in the worst case scenario since the loop runs from index`i = 2` to`i = n`. This time complexity can be reduced from`O(n)` to`O(sqrt(n))`. The optimisation is achievable when loop runs from`i = 2` to`i = sqrt(n)`. Now, we go only till`O(sqrt(n))` because when`i` becomes greater than`sqrt(n)`, we have the confirmation that there is no index`i` left which can divide`n` completely other than`n` itself.
2322

24-
- getPrimeFactorsCount: returns accurate total countofdistinctprime factors of given input n.
23+
##Hardy-Ramanujan formula for approximate calculationof prime-factor count
2524

26-
- hardyRamanujanApprox: returns approximate total countof distinct prime factors ofgiven input n using Hardy-Ramanujan formula.
25+
In 1917, a theorem was formulated by G.H Hardy and Srinivasa Ramanujan which states that the normal orderofthe number`ω(n)` ofdistinct prime factors ofa number`n` is`log(log(n))`.
2726

28-
- errorPercent : returns %age of error in approximation using formula to that of accurate result. The formula used is:**[Modulus(accurate_val - approximate_val) / accurate_val] * 100**. This shows deviation from accurate result.
29-
27+
Roughly speaking, this means that most numbers have about this number of distinct prime factors.
3028

3129
##References
3230

33-
-[Youtube](https://www.youtube.com/watch?v=6PDtgHhpCHo)
34-
-[Wikipedia](https://en.wikipedia.org/wiki/Hardy%E2%80%93Ramanujan_theorem)
31+
-[Prime numbers on Math is Fun](https://www.mathsisfun.com/prime-factorization.html)
32+
-[Prime numbers on Wikipedia](https://en.wikipedia.org/wiki/Prime_number)
33+
-[Hardy–Ramanujan theorem on Wikipedia](https://en.wikipedia.org/wiki/Hardy%E2%80%93Ramanujan_theorem)
34+
-[Prime factorization of a number on Youtube](https://www.youtube.com/watch?v=6PDtgHhpCHo&list=PLLXdhg_r2hKA7DPDsunoDZ-Z769jWn4R8&index=82)
Lines changed: 87 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,87 @@
1+
import{
2+
primeFactors,
3+
hardyRamanujan,
4+
}from'../primeFactors';
5+
6+
/**
7+
* Calculates the error between exact and approximate prime factor counts.
8+
*@param {number} exactCount
9+
*@param {number} approximateCount
10+
*@returns {number} - approximation error (percentage).
11+
*/
12+
functionapproximationError(exactCount,approximateCount){
13+
return(Math.abs((exactCount-approximateCount)/exactCount)*100);
14+
}
15+
16+
describe('primeFactors',()=>{
17+
it('should find prime factors',()=>{
18+
expect(primeFactors(1)).toEqual([]);
19+
expect(primeFactors(2)).toEqual([2]);
20+
expect(primeFactors(3)).toEqual([3]);
21+
expect(primeFactors(4)).toEqual([2,2]);
22+
expect(primeFactors(14)).toEqual([2,7]);
23+
expect(primeFactors(40)).toEqual([2,2,2,5]);
24+
expect(primeFactors(54)).toEqual([2,3,3,3]);
25+
expect(primeFactors(100)).toEqual([2,2,5,5]);
26+
expect(primeFactors(156)).toEqual([2,2,3,13]);
27+
expect(primeFactors(273)).toEqual([3,7,13]);
28+
expect(primeFactors(300)).toEqual([2,2,3,5,5]);
29+
expect(primeFactors(980)).toEqual([2,2,5,7,7]);
30+
expect(primeFactors(1000)).toEqual([2,2,2,5,5,5]);
31+
expect(primeFactors(52734)).toEqual([2,3,11,17,47]);
32+
expect(primeFactors(343434)).toEqual([2,3,7,13,17,37]);
33+
expect(primeFactors(456745)).toEqual([5,167,547]);
34+
expect(primeFactors(510510)).toEqual([2,3,5,7,11,13,17]);
35+
expect(primeFactors(8735463)).toEqual([3,3,11,88237]);
36+
expect(primeFactors(873452453)).toEqual([149,1637,3581]);
37+
});
38+
39+
it('should give approximate prime factors count using Hardy-Ramanujan theorem',()=>{
40+
expect(hardyRamanujan(2)).toBeCloseTo(-0.366,2);
41+
expect(hardyRamanujan(4)).toBeCloseTo(0.326,2);
42+
expect(hardyRamanujan(40)).toBeCloseTo(1.305,2);
43+
expect(hardyRamanujan(156)).toBeCloseTo(1.6193,2);
44+
expect(hardyRamanujan(980)).toBeCloseTo(1.929,2);
45+
expect(hardyRamanujan(52734)).toBeCloseTo(2.386,2);
46+
expect(hardyRamanujan(343434)).toBeCloseTo(2.545,2);
47+
expect(hardyRamanujan(456745)).toBeCloseTo(2.567,2);
48+
expect(hardyRamanujan(510510)).toBeCloseTo(2.575,2);
49+
expect(hardyRamanujan(8735463)).toBeCloseTo(2.771,2);
50+
expect(hardyRamanujan(873452453)).toBeCloseTo(3.024,2);
51+
});
52+
53+
it('should give correct deviation between exact and approx counts',()=>{
54+
expect(approximationError(primeFactors(2).length,hardyRamanujan(2)))
55+
.toBeCloseTo(136.651,2);
56+
57+
expect(approximationError(primeFactors(4).length,hardyRamanujan(2)))
58+
.toBeCloseTo(118.325,2);
59+
60+
expect(approximationError(primeFactors(40).length,hardyRamanujan(2)))
61+
.toBeCloseTo(109.162,2);
62+
63+
expect(approximationError(primeFactors(156).length,hardyRamanujan(2)))
64+
.toBeCloseTo(109.162,2);
65+
66+
expect(approximationError(primeFactors(980).length,hardyRamanujan(2)))
67+
.toBeCloseTo(107.330,2);
68+
69+
expect(approximationError(primeFactors(52734).length,hardyRamanujan(52734)))
70+
.toBeCloseTo(52.274,2);
71+
72+
expect(approximationError(primeFactors(343434).length,hardyRamanujan(343434)))
73+
.toBeCloseTo(57.578,2);
74+
75+
expect(approximationError(primeFactors(456745).length,hardyRamanujan(456745)))
76+
.toBeCloseTo(14.420,2);
77+
78+
expect(approximationError(primeFactors(510510).length,hardyRamanujan(510510)))
79+
.toBeCloseTo(63.201,2);
80+
81+
expect(approximationError(primeFactors(8735463).length,hardyRamanujan(8735463)))
82+
.toBeCloseTo(30.712,2);
83+
84+
expect(approximationError(primeFactors(873452453).length,hardyRamanujan(873452453)))
85+
.toBeCloseTo(0.823,2);
86+
});
87+
});

‎src/algorithms/math/prime-factors/__test__/primefactors.test.js

Lines changed: 0 additions & 40 deletions
This file was deleted.
Lines changed: 42 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,42 @@
1+
/**
2+
* Finds prime factors of a number.
3+
*
4+
*@param {number} n - the number that is going to be split into prime factors.
5+
*@returns {number[]} - array of prime factors.
6+
*/
7+
exportfunctionprimeFactors(n){
8+
// Clone n to avoid function arguments override.
9+
letnn=n;
10+
11+
// Array that stores the all the prime factors.
12+
constfactors=[];
13+
14+
// Running the loop till sqrt(n) instead of n to optimise time complexity from O(n) to O(sqrt(n)).
15+
for(letfactor=2;factor<=Math.sqrt(nn);factor+=1){
16+
// Check that factor divides n without a reminder.
17+
while(nn%factor===0){
18+
// Overriding the value of n.
19+
nn/=factor;
20+
// Saving the factor.
21+
factors.push(factor);
22+
}
23+
}
24+
25+
// The ultimate reminder should be a last prime factor,
26+
// unless it is not 1 (since 1 is not a prime number).
27+
if(nn!==1){
28+
factors.push(nn);
29+
}
30+
31+
returnfactors;
32+
}
33+
34+
/**
35+
* Hardy-Ramanujan approximation of prime factors count.
36+
*
37+
*@param {number} n
38+
*@returns {number} - approximate number of prime factors.
39+
*/
40+
exportfunctionhardyRamanujan(n){
41+
returnMath.log(Math.log(n));
42+
}

‎src/algorithms/math/prime-factors/primefactors.js

Lines changed: 0 additions & 44 deletions
This file was deleted.

0 commit comments

Comments
 (0)
[8]ページ先頭
©2009-2025 Movatter.jp