Algorithm to find GCD using Stein’s algorithm gcd(a,b) If both and b are 0, gcd is zero gcd(0, 0) = 0. gcd(a, 0) = a and gcd(0, b) = b because everything divides 0. If a and b are both even, gcd(a, b) = 2*gcd(a/2, b/2) because 2 is a common divisor. Multiplication with 2
Month: September 2016
Word Break [ IBM – Google ]
Problem: Given an input string and a dictionary of words, find out if the input string can be segmented into a space-separated sequence of dictionary words. See following examples for more details. Consider the following dictionary { i, like, sam, sung, samsung, mobile, ice,cream, icecream, man, go, mango} Input: ilike Output: Yes The string can be
Almost Prime number
Problem:A no is said to be k-Almost Prime Number if it has exactly k prime factors (not necessary distinct). Your task is to complete the functionprintKAlmostPrimes which takes two argument k and N and prints the first N numbers that are k prime. Problem Link
|
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 |
/*You are required to complete this function*/ bool isPrime(int n) { bool arr[20]; int i; arr[2]=1;arr[3]=1;arr[5]=1;arr[7]=1; arr[11]=1;arr[13]=1;arr[17]=1;arr[19]=1; if(n<20) { if(arr[n]==1) return 1; else if(arr[n]==0) return 0; } if(n%2==0) return 0; for(i=3;i<=sqrt(n);i+=2) { if(n%i==0) return 0; } return 1; } int CountOfPrime(int n) { int cnt=0,i; while(n%2==0) { cnt+=1; n/=2; } for(i=3;i<=sqrt(n);i+=2) { if(isPrime(i)==0) continue; while(n%i==0) { cnt+=1; n/=i; } } if(n>2) cnt+=1; return cnt; } void printKAlmostPrimes(int k, int n) { //Your code here int i,num; for(i=1,num=2;i<=n;num++) { if(CountOfPrime(num)==k) { printf("%d ",num); i++; } } } |