How many numbers 1 - n are divisible by a range of primes

Question

Hello there was interesting simple math problem I have recently solved : - How many positive integers in a range 1 to n are divisible by at least one of given primes ? Here is the recursive function that solves the problem : // n range of numbers from 1 to n // p array of primes for divisibility check long f( long n long [] p) { if (p.Length==0) return 0; long [] q = new long [p.Length-1]; Array.Copy(p1q0p.Length-1); long r = (n/p[0])- (f(n/p[0]q)) + (f(nq)); return r; } My question is : - Is it possible to write this function in C# differently so that its execution becomes faster ? All the best Željko Peric

Dharmraj Thakur · Answer

You can do it without recursive using linq static void Main( string [] args) { long [] rng = { 35 }; var result = FindNums(20 rng); Console.ReadKey(); } public static List int > FindNums( long n long [] rng) { List int > result = new List int >(); for ( int i = 1; i { var res = rng.Where(m => m > 0 && (i % m == 0)); if (res.Count() > 0) { result.Add(i); } } return result; }

Dharmraj Thakur · Answer

Compare this once... static void Main( string [] args) { long [] rng = { 3 5 }; var result = FindNums(20 rng); Console.ReadKey(); } public static string FindNums( long n long [] rng) { StringBuilder result = new StringBuilder(); for ( int i = 1; i { if (rng.Where(m => m > 0 && (i % m == 0)).Count() > 0) { result.Append(i).Append(  ); } } return result.ToString(); }

Željko Perić · Answer

Solution given by Dharmraj Thakur is mathematically correct but it can't be accepted as answer because it is way too slow. exmpl: long n = 100 000 000 - range of numbers 1 - 100 000 000 long [ ] p = new p[3]{5711} - prime numbers for divisibility check 5 7 11 long r = 37662339 divisible numbers counted this is correct result execution time is 441060756 milliseconds with linq and execution time is 432750199 milliseconds with stringbuilder It is even slower than this solution that do the same thing with for..next.../for...each loop and modulo function as solution that uses linq library execution time is 119115324 milliseconds // n range of numbers from 1 to n // p array of primes for divisibility check long f( long n long [] p) { long k = 0; for ( long i = 1; i { foreach ( long prime in p) { if (i%prime==0) { k++; break ; } } } return k; } And far too slow comparing to the proposed final solution given at question above with recursive function and execution time 04598 milliseconds. Anyway thanks for correct solution All the best Željko Peric.