Sexy primes: Difference between revisions
no edit summary
No edit summary |
No edit summary |
||
Line 301:
[[999853 999863 999883 999907 999917 999931 999961 999979 999983 1000003]
</pre>
=={{header|C++}}==
<lang cpp>
#include <iostream>
#include <vector>
int main()
{
using std::cout;
using std::vector;
const int max = 1000035;
const int max_group_size = 5;
const int diff = 6;
const int array_size = max + diff;
const int max_groups = 5;
const int max_unsexy = 10;
// Use Sieve of Eratosthenes to find prime numbers up to max
vector<bool> isprime(array_size, true);
for (int p = 2; p * p < array_size; ++p)
{
if (isprime[p])
{
for (int i = p * p; i < array_size; i += p)
isprime[i] = false;
}
}
vector<int> group_count(max_group_size);
vector<vector<vector<int>>> groups(max_group_size);
int unsexy_count = 0;
vector<int> unsexy_primes;
for (int p = 2; p < max; )
{
if (!isprime[p + diff] && (p - diff < 2 || !isprime[p - diff]))
{
// if p + diff and p - diff aren't prime then p can't be sexy
++unsexy_count;
if (unsexy_primes.size() == max_unsexy)
unsexy_primes.erase(unsexy_primes.begin());
unsexy_primes.push_back(p);
}
else
{
// find the groups of sexy primes that begin with p
int group_size = 1;
vector<int> group;
group.push_back(p);
for (int i = 1; i < max_group_size; ++i)
{
int next_p = p + i * diff;
if (next_p >= max || !isprime[next_p])
break;
++group_size;
group.push_back(next_p);
vector<vector<int>>& v = groups[group_size - 1];
if (v.size() == max_groups)
v.erase(v.begin());
v.push_back(group);
}
for (int i = 1; i < group_size; ++i)
++group_count[i];
}
// skip to next prime number
++p;
while (p < max && !isprime[p])
++p;
}
for (int size = 1; size < max_group_size; ++size)
{
cout << "number of groups of size " << size + 1 << " is " << group_count[size] << '\n';
cout << "last " << groups[size].size() << " groups of size " << size + 1 << ":";
for (const vector<int>& group : groups[size])
{
cout << " (";
for (size_t i = 0; i < group.size(); ++i)
{
if (i > 0)
cout << ' ';
cout << group[i];
}
cout << ")";
}
cout << "\n\n";
}
cout << "number of unsexy primes is " << unsexy_count << '\n';
cout << "last " << unsexy_primes.size() << " unsexy primes:";
for (int prime : unsexy_primes)
cout << ' ' << prime;
cout << '\n';
return 0;
}
</lang>
{{out}}
<pre>
number of groups of size 2 is 16386
last 5 groups of size 2: (999371 999377) (999431 999437) (999721 999727) (999763 999769) (999953 999959)
number of groups of size 3 is 2900
last 5 groups of size 3: (997427 997433 997439) (997541 997547 997553) (998071 998077 998083) (998617 998623 998629) (998737 998743 998749)
number of groups of size 4 is 325
last 5 groups of size 4: (977351 977357 977363 977369) (983771 983777 983783 983789) (986131 986137 986143 986149) (990371 990377 990383 990389) (997091 997097 997103 997109)
number of groups of size 5 is 1
last 1 groups of size 5: (5 11 17 23 29)
number of unsexy primes is 48627
last 10 unsexy primes: 999853 999863 999883 999907 999917 999931 999961 999979 999983 1000003
</pre>
=={{header|F_Sharp|F#}}==
This task uses [http://www.rosettacode.org/wiki/Extensible_prime_generator#The_function Extensible Prime Generator (F#)]
| |||