You are using a version without Ads of this website. Please, consider donating:

Challenge Problem

Here is a fairly simple programming challenge; an opportunity for some of the young talent to show their skills.

Respect will be awarded to the programmer who writes the most time efficient solution (multithreading welcome), the most interesting solution (recursion welcome), and the most elegant solution.

For the first 9 prime numbers (excluding 2),

3, 5, 7, 11, 13, 17, 19, 23, 29

3 + 7 = 10
5 + 11 = 16
7 + 13 = 20
11 + 17 = 28
13 + 19 = 32
17 + 23 = 40
19 + 29 = 48

10 + 20 = 30
16 + 28 = 44
20 + 32 = 52
28 + 40 = 68
32 + 48 = 80

44 - 30 = 14
52 - 44 = 8
68 - 52 = 16
80 - 68 = 12

The sequence: 14, 8, 16, 12 (for primes 3 through 29)

Your program should output the described sequence for primes from 3 to n.
After the sequence has been printed, print the maximum value in the sequence,
the minimum value in the sequence, the most commonly occurring value in the sequence (mode) (multiple if there is a tie), and the largest integer gap between consecutive terms in the sequence.

example output:

 primes 3 to 29 (14, 8, 16, 12) Max: 16 Min: 8 Mode: 14, 8, 16, 12 Largest Gap: 8

Last edited on
Which libraries are we allowed to use?
You can use anything you want.
Dang, I wish I was more familiar with boost.
What would the upper limit on n be?
n should be set through user input.

Respect will also be awarded for wise/creative use of libraries (including the STL), and language features.
Last edited on
 n should be set through user input

obviously, but algorithms might differ if n is <200 vs if n in <2000
must we just expect really high values of n?
 obviously, but algorithms might differ if n is <200 vs if n in <2000 must we just expect really high values of n?

Last edited on
LB wrote:
Which libraries are we allowed to use?
iseeplusplus wrote:
You can use anything you want.
Shortest solution:
 12345 void doStuff(); int main() { doStuff(); }
Last edited on
All libraries have to be open source, then. I'm sure we can all agree :p

Still, thought, MiiNiPaa does raise a point - some libraries make this task blisteringly easy and elegant, even if their implementation is not.
Last edited on
 All libraries have to be open source, then. I'm sure we can all agree :p Still, thought, MiiNiPaa does raise a point - some libraries make this task blisteringly easy and elegant, even if their implementation is not.

True, but you would only "win" best use of libraries "award" for that.
Last edited on
I suggest to use only standard C++.
So no boost, no specific math libraries.
 I suggest to use only standard C++. So no boost, no specific math libraries.

Ok.
Last edited on
Well I decided to give this problem a go in Python to see if I am actually learning anything from the last 2 days lol and because you didn't give a language restriction for this problem ;p.

Anyways here is my attempt, it seems to be working though I didn't do much testing on it since it is 5:30am and I just want to head to bed. It does run quite slowly if you get to numbers above 100k though but that is ok for now I will make it more efficient tomorrow.

 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172 from collections import Counter def primes(n): s = range(3,n+1,2) mroot = n ** 0.5 half = (n+1) / 2-1 i = 0 m = 3 while m <= mroot: if s[i]: j = (m*m-3) / 2 s[j] = 0 while j < half: s[j] = 0 j += m i = i + 1 m = 2 * i + 3 return [x for x in s if x] def first_stage(primeList): newList = [] for each in range(len(primeList)): if each + 2 >= len(primeList): break number = primeList[each] + primeList[each+2] newList.append(number) return newList def second_stage(myList): newList = [] for each in range(len(myList)): if each + 2 >= len(myList): break newList.append(myList[each] + myList[each+2]) return newList def third_stage(myList): newList = [] for each in range(len(myList)): if each + 1 >= len(myList): break newList.append(myList[each+1] - myList[each]) return newList def find_greatest_difference(myList): gaps = [] for each in range(len(myList) - 1): if myList[each] < myList[each+1]: gaps.append(myList[each+1] - myList[each]) else: gaps.append(myList[each] - myList[each+1]) return max(gaps) def find_mode(myList): count = Counter(myList) freq_list = count.values() max_count = max(freq_list) total = freq_list.count(max_count) return count.most_common(total) limit = int(raw_input("Enter a max number:")) myList = primes(limit) myList = first_stage(myList) myList = second_stage(myList) myList = third_stage(myList) print "Primes ", 3, " to ", limit print myList print "Max:", max(myList) print "Min:", min(myList) print "Mode (Number/Times Found):", find_mode(myList) print "Largest Gap:", find_greatest_difference(myList)
Last edited on
Technically, since Python is written in C using only the C standard library (AFAIK), of which the C++ standard library is a superset, a Python solution counts as a C++ one.
C++ libraries are usually implemented using C/C++ standard libraries and C++ base language features, so almost any C++ library will counts as base C++ by your logic.

I think we should allow any language which uses only its owb standard libraries.
Fixed my solution to output the correct values for mode. Now working on the performance a bit (Though it runs pretty fast now for numbers up to a few million or so), and adding in some fun tricks to make it more elegant ;p Though I gotta look up some more features of Python first :(

Ohh ya nice little programming problem iseeplusplus was fun to work on.
Last edited on
Topic archived. No new replies allowed.

You are using a version without Ads of this website. Please, consider donating: