FCTRL - Factorial

See on SPOJ

The most important part of a GSM network is so called Base Transceiver Station (BTS). These transceivers form the areas called cells (this term gave the name to the cellular phone) and every phone connects to the BTS with the strongest signal (in a little simplified view). Of course, BTSes need some attention and technicians need to check their function periodically.

ACM technicians faced a very interesting problem recently. Given a set of BTSes to visit, they needed to find the shortest path to visit all of the given points and return back to the central company building. Programmers have spent several months studying this problem but with no results. They were unable to find the solution fast enough. After a long time, one of the programmers found this problem in a conference article. Unfortunately, he found that the problem is so called "Travelling Salesman Problem" and it is very hard to solve. If we have N BTSes to be visited, we can visit them in any order, giving us N! possibilities to examine. The function expressing that number is called factorial and can be computed as a product 1.2.3.4....N. The number is very high even for a relatively small N.

The programmers understood they had no chance to solve the problem. But because they have already received the research grant from the government, they needed to continue with their studies and produce at least some results. So they started to study behaviour of the factorial function.
For example, they defined the function Z. For any positive integer N, Z(N) is the number of zeros at the end of the decimal form of number N!. They noticed that this function never decreases. If we have two numbers N₁<N₂, then Z(N₁) <= Z(N₂). It is because we can never "lose" any trailing zero by multiplying by any positive number. We can only get new and new zeros. The function Z is very interesting, so we need a computer program that can determine its value efficiently.


Simply you have to find the number of zero's at the end of N! (factorial(N))

Input

There is a single positive integer T on the first line of input (equal to about 100000). It stands for the number of numbers to follow. Then there are T lines, each containing exactly one positive integer number N, 1 <= N <= 1000000000.

 

Output

For every number N, output a single line containing the single non-negative integer Z(N).

 

Example

Sample Input:

6
3
60
100
1024
23456
8735373

Sample Output:

0
14
24
253
5861
2183837

Solution- count Number of 5's.

 

Yeah, that's it. You just to calculate the number the of 5's in the prime factorization of N!.

This is because it is obvious for any factorial to have more number of 2's than 5's in its prime factorization. Thus every 5 which appears in factorization will get a 2 so that it can be multiplied with it to become 10. And it is pretty clear that the number of occurrences of 10 in factorization is the same as the number of 0's at the end.

Logic-

Suppose we have number 100. we need to calculate the number of 5 in the prime factorization of 100!.

We know 100!=1*2*3*4*5....*100

Let zeros= number of zeros initially zero.

Thus every number divisible by 5 (like 5,10,15..95,100) will give one 5 as a factor.

zeros+=(100/5)=20

Similarly numbers divisible by 5*5=25 (like 25,50, 75,100) will give two 5's as factors.

(Since one five is already taken into account)

zeros+=100/25... =24

Now 5^3=125>N(100) thus we stop here.

And the answer is 24.

Simple C++ Implementation is here . Time Taken =0.01 sec.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38

//zero in factorial #include <bits/stdc++.h> int main() {int a,zeros,num,i,t,j; scanf("%d",&t); while(t--) { scanf("%d",&num); a=5; zeros=0 ; while(num/a!=0) { zeros+=num/a; a=a*5; //increasing a to powers of 5 } printf("\n%d",zeros); } return 0; }

PRIME1 - Prime Generator

See on SPOJ


Peter wants to generate some prime numbers for his cryptosystem. Help him! Your task is to generate all prime numbers between two given numbers!

 

Input

The input begins with the number t of test cases in a single line (t<=10). In each of the next t lines there are two numbers m and n (1 <= m <= n <= 1000000000, n-m<=100000) separated by a space.

 

Output

For every test case print all prime numbers p such that m <= p <= n, one number per line, test cases separated by an empty line.

 

Example

Input:
2
1 10
3 5

Output:
2
3
5
7

3
5

First Solution- Brute Force

 

Yeah, Brute force works too. Though the given constraints are large enough to fail this method, But if you implement it smartly, it will work.

Just check for every number in the range with the check prime() method and print it.

NOTE: This Solution is not recommended. But due to nonexhaustive test cases, it gets through with Time 0.93 sec. 

The Trick behind this is to use as less memory as you can, thus all operation takes place in cache hence runs really fast.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52

#include<iostream> #include<math.h> #include<stdio.h> using namespace std; bool checkprime (long int num) { if (num <=1) return false; else if (num == 2) return true; else if (num % 2 == 0) return false; else { bool prime = true; int divisor = 3; int upperLimit =sqrt(num) +1; while (divisor <= upperLimit) { if (num % divisor == 0) return false; divisor +=2; } return prime; } } int main() {int a,b,i,n,j; scanf("%d",&n); for(i=0;i<n;i++) { scanf(" %d %d",&a,&b); printf("\n"); for(j=a;j<=b;j++) { if(checkprime(j)) printf("%d\n",j); } } return 0; }

 

Second Solution- Segmented Sieve Of Eratosthenes

Learn on Wiki

The primes need to be found using the Sieve Of Eratosthenes. However, that is also not enough. The traditional Sieve of Eratosthenes gives us the list of prime numbers till a number N. Here we need to find the prime numbers between M and N.So we need a modified form of Sieve of Eratosthenes which works on the same basic principle but only finds the primes within a range called Segmented Sieve Of Eratosthenes. Go ahead at this point, check out the Wikipedia article on these subjects.

Logic:
We know that 2 is the first prime no. So, if we start from 2(excluding 2) and increment in 2 steps(that is i=i+2) all numbers we get are divisible by 2 at least. So they cannot be prime.So all those numbers we remove from the list(here removal from the list is done by making segment[]=true for that number). Then the next bigger number that is still on the list will surely be a prime number. In our case, it is 3.  3 is a prime number. We start from 3 and increment in steps of 3, we cut-off 6,9,12, and so on. After 2 and 3, the next largest number in the list that has not been removed is 5. Since 4 has only been cut off as it is a composite of 2. We cut 10,15,20 and so on till N.In this way we remove composite numbers and after a while, the list contains only prime numbers.

Segmented Sieve
Say I need to find the prime numbers between 125 and 140. One way is to find all primes till 140 using traditional sieves and then find how many of them are greater than 125. This will not work within limited time constraints. We need to fit the Sieve to our needs so that we run the Sieve only in that particular range.

The first prime is 2.We divide the starting number x=125 by 2.We round off to smaller integer we get 62. We again multiply by 2 we get 124. What is 124? it is the first smaller number than x that is divisible by the prime 2.We start from 124, increment by 2 in each step, and remove all elements between 125 and 140. That is we remove 126,128,130,132,134,136,138,140.What we did was that we did the first step in a traditional sieve but just offset the starting elements to the closest composite number less than the starting point of the range. Next, we do this with the 2nd smallest prime number 3.125/3=41.41*3=123.We start from 123 go till 140 (inclusive) in steps of 3 and cut the numbers 126,129,132,135,138.Next, we do with 5. But from where do we get the prime numbers 2,3,5 and so on and how long do we need to do that?

We must first use a traditional sieve to make a list of primes up to sqrt(N) where N is the larger of the range. Then we will use this list of primes in the segmented sieve operation. This will leave us with the prime numbers in the desired range. Please re-read the above part a number of times and get this concept clear or revert back in case of any query.

The Trick behind this is to use as less memory as you can, thus all operation takes place in cache hence runs really fast. If you increase the segment size then it may give TLE.

This method Decreases the time taken to 0.01 sec.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123

//generate Prime using sieve //segmented sieve //limits the memory used, thus inside cache only hence speed up #include <bits/stdc++.h> #define max1(x,y) (x)>(y)?(x):(y) #define s(n) scanint(n) #define sc(n) scanf(" %c",&n) #define sl(n) scanf("%ld",&n) #define sll(n) scanf("%lld",&n) #define sf(n) scanf("%lf",&n) #define ss(n) scanf("%s",n) #define INF (int)1e9 #define EPS 1e-9 #define bitcount __builtin_popcount #define gcd __gcd #define forall(i,a,b) for(int i=a;i<b;i++) #define all(a) a.begin(), a.end() #define pb push_back #define sz(a) ((int)(a.size())) #define mp make_pair #define checkbit(n,b) ( (n >> b) & 1) #define gc getchar_unlocked #define l long using namespace std ; inline void scanint(int &x) { register int c = gc(); x = 0; int neg = 0; for(;((c<48 || c>57) && c != '-');c = gc()); if(c=='-') {neg=1;c=gc();} for(;c>47 && c<58;c = gc()) {x = (x<<1) + (x<<3) + c - 48;} if(neg) x=-x; } vector<int > primeArray; bool check[50009]; int keep = 1; void initialise() { check[1 ] = 1; for(int i = 3 ; i <=224 ; i+=2){ if(!check[i]){ for(int j = i*i ; j<= 50000 ; j+=2*i) check[j] = true; } } primeArray.pb(2); keep=1; for(int i = 3 ; i<= 50000 ; i++) if(check[i] == false && (i&1)) primeArray.pb(i) , keep++; } bool segment[1000009]; int main() { int t; s(t); initialise(); while(t--) { int a , b; s(a),s(b); if(b <= 50000){ if(a<=2) printf("2\n"); for(int i = a ; i<= b ; i++){ if(check[i] == false && (i&1)) printf("%d\n", i); } continue; } memset(segment , 0 , sizeof segment); for(int i = 0; primeArray[i]*primeArray[i] <= b ; i++) { int begin = a/primeArray[i]; begin *= primeArray[i]; for(int j = begin ; j<= b ; j+= primeArray[i]){ if(j < a) continue; segment[j - a] = true; } } for(int i = 0 ; primeArray[i]*primeArray[i] <= b ; i++){ if(primeArray[i]>= a && primeArray[i]<=b) printf("%d\n",primeArray[i]); } for(int i = a==1?1:0 ; i < b-a+1 ; i++) if(segment[i]==0) printf("%d\n", i+a); } return 0; }