HOME/Algorithm/

Find four primes

Article Outline
TOC
Collection Outline

Find four primes

Recently I was looking for a job. Most companies send a paper test before on-site interview.

Last month, I received a test as below:

I have four different prime number all under 1000. I have noticed that the product of these primes is a twelve-digit number whose digits are either sequential or the same as previous one.

What are the four digits?


 public int[] FindFourPrimes(int N)  {
            var primes = Primes(N);
            var lstPrimes = new List<int>();
            for(var i = 0; i < N; i++) {
                if(primes[i]) {
                    lstPrimes.Add(i);
                }
            }

            for(var a = 0; a < lstPrimes.Count(); a++) {
                for(var b = a+1; b < lstPrimes.Count(); b++) {
                    for(var c = b+1; c < lstPrimes.Count(); c++) {
                        for(var d = c+1; d < lstPrimes.Count(); d++) {
                            if(IsSeqInt((long)lstPrimes[a]*lstPrimes[b] * lstPrimes[c] *lstPrimes[d])) {
                                return new int[] {lstPrimes[a],lstPrimes[b],lstPrimes[c],lstPrimes[d]};
                            }
                        }
                    }
                }
            }

            return null;
        }

        public bool IsSeqInt(long n)
        {
            var str = n.ToString();
            if(str.Length != 12) return false;

            for(var i = 0; i < str.Length-1; i++) {
                if(str[i] != str[i+1] && Math.Abs(str[i]-str[i+1]) != 1) {
                    return false;
                }
            }

            return true;
        }

        public bool[] Primes(int N)
        {
            var ret = new bool[N+1];
            for(int i = 2; i < N+1; i++)
            {
                ret[i] = true;
            }
            for(int i = 2; i*i <= N; i++)
            {
                if(ret[i])
                {
                    var ite = i * 2;
                    while(ite < N+1)
                    {
                        ret[ite] = false;
                        ite += i;
                    }
                }
            }

            return ret;
        }

One of the results is : 863 * 811 * 563 * 313 = 123334444567