UVa 412

From Algorithmist
Jump to navigation Jump to search

412 - Pi[edit]

Also seen:

Summary[edit]

Given a list of integers, determine the value of pi using the ratio of pairs without a common factor other than 1, and the total number of pairs.

Explanation[edit]

Given a large collection of integers, the probability of finding a pair of numbers that have no common factors other than 1 is approximatly 6/pi^2.

After counting the number of pairs of numbers, you can use basic algebra to determine the value of pi. However, there are some number sets that do not have pairs without common factors, which would result in a division by zero.

Gotchas[edit]

  • 1 doesn't share common factors greater than 1 with any other number.
  • The limits specified for the problem on UVA is not correct - they appear to include numbers greater than 32768. However, you can still use the Euler's GCF function without difficulty.

Input[edit]

5
2
3
4
5
6
2
13
39
0

Output[edit]

3.162278
No estimate for this data set.

Solutions[edit]