n-th prime number problem, need to speed it up a bit
https://stackoverflow.com/questions/929712
-
06-09-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianQuestion
There is simple cipher that translates number to series of . ( )
In order to encrypt a number (0 .. 2147483647) to this representation, I (think I) need:
- prime factorization
- for given p (p is Prime), order sequence of p (ie. PrimeOrd(2) == 0, PrimeOrd(227) == 49)
Some examples
0 . 6 (()())
1 () 7 (...())
2 (()) 8 ((.()))
3 (.()) 9 (.(()))
4 ((())) 10 (().())
5 (..()) 11 (....())
227 (................................................())
2147483648 ((..........()))
My source code for the problem
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.IO;
static class P
{
static List<int> _list = new List<int>();
public static int Nth(int n)
{
if (_list.Count == 0 || _list.Count < n)
Primes().Take(n + 1);
return _list[n];
}
public static int PrimeOrd(int prime)
{
if (_list.Count == 0 || _list.Last() < prime)
Primes().First(p => p >= prime);
return (_list.Contains(prime)) ? _list.FindIndex(p => p == prime) : -1;
}
public static List<int> Factor(int N)
{
List<int> ret = new List<int>();
for (int i = 2; i ≤ N; i++)
while (N % i == 0)
{
N /= i;
ret.Add(i);
}
return ret;
}
public static IEnumerable<int> Primes()
{
_list = new List<int>();
_list.Add(2);
yield return 2;
Func<int, bool> IsPrime = n => _list.TakeWhile(p => p ≤ (int)Math.Sqrt(n)).FirstOrDefault(p => n % p == 0) == 0;
for (int i = 3; i < Int32.MaxValue; i += 2)
{
if (IsPrime(i))
{
_list.Add(i);
yield return i;
}
}
}
public static string Convert(int n)
{
if (n == 0) return ".";
if (n == 1) return "()";
StringBuilder sb = new StringBuilder();
var p = Factor(n);
var max = PrimeOrd(p.Last());
for (int i = 0; i ≤ max; i++)
{
var power = p.FindAll((x) => x == Nth(i)).Count;
sb.Append(Convert(power));
}
return "(" + sb.ToString() + ")";
}
}
class Program
{
static void Main(string[] args)
{
string line = Console.ReadLine();
try
{
int num = int.Parse(line);
Console.WriteLine("{0}: '{1}'", num, P.Convert(num));
}
catch
{
Console.WriteLine("You didn't entered number!");
}
}
}
The problem is SLOWNESS of procedure PrimeOrd. Do you know some FASTER solution for finding out order of prime in primes?
Heading
If You know how to speed-up finding order of prime number, please, suggest something. :-)
Thank You.
P.S. The biggest prime less than 2,147,483,648 is 2,147,483,647 and it's 105,097,565th prime. There is no need to expect bigger number than 2^31.
Solution
You should cache the primes to _list and then use it for both Factor and PrimeOrd. Additionally avoid operators LINQ operators like TakeWhile that create values that you throw away.
Here's an optimized version:
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
static class P
{
private static List<int> _list = new List<int>();
public static int Nth(int n)
{
if (_list.Count == 0 || _list.Count <= n)
{
GenerateNextPrimes().First(p => _list.Count >= n);
}
return _list[n];
}
public static int PrimeOrd(int prime)
{
var primes = GrowPrimesTo(prime);
return primes.IndexOf(prime);
}
public static List<int> Factor(int N)
{
List<int> ret = new List<int>();
GrowPrimesTo(N);
for (int ixDivisor = 0; ixDivisor < _list.Count; ixDivisor++)
{
int currentDivisor = _list[ixDivisor];
while (N % currentDivisor == 0)
{
N /= currentDivisor;
ret.Add(currentDivisor);
}
if (N <= 1)
{
break;
}
}
return ret;
}
private static List<int> GrowPrimesTo(int max)
{
if (_list.LastOrDefault() >= max)
{
return _list;
}
GenerateNextPrimes().First(prime => prime >= max);
return _list;
}
private static IEnumerable<int> GenerateNextPrimes()
{
if (_list.Count == 0)
{
_list.Add(2);
yield return 2;
}
Func<int, bool> IsPrime =
n =>
{
// cache upperBound
int upperBound = (int)Math.Sqrt(n);
for (int ixPrime = 0; ixPrime < _list.Count; ixPrime++)
{
int currentDivisor = _list[ixPrime];
if (currentDivisor > upperBound)
{
return true;
}
if ((n % currentDivisor) == 0)
{
return false;
}
}
return true;
};
// Always start on next odd number
int startNum = _list.Count == 1 ? 3 : _list[_list.Count - 1] + 2;
for (int i = startNum; i < Int32.MaxValue; i += 2)
{
if (IsPrime(i))
{
_list.Add(i);
yield return i;
}
}
}
public static string Convert(int n)
{
if (n == 0) return ".";
if (n == 1) return "()";
StringBuilder sb = new StringBuilder();
var p = Factor(n);
var max = PrimeOrd(p.Last());
for (int i = 0; i <= max; i++)
{
var power = p.FindAll(x => x == Nth(i)).Count;
sb.Append(Convert(power));
}
return "(" + sb.ToString() + ")";
}
}
class Program
{
static void Main(string[] args)
{
string line = Console.ReadLine();
int num;
if(int.TryParse(line, out num))
{
Console.WriteLine("{0}: '{1}'", num, P.Convert(num));
}
else
{
Console.WriteLine("You didn't entered number!");
}
}
}
OTHER TIPS
This is not something you should be doing at run-time. A better option is to pre-calculate all these primes and then put them in your program somehow (a static array, or a file to be read in). The slow code is then run as part of the development process (which is slow anyway :-), not at the point where you need your speed.
Then it's just a matter of a lookup of some sort rather than calculating them every time you need them.
Please see SO questions:
http://www.google.com/search?q=site%3Astackoverflow.com+prime+number&btnG=Search
How can I find prime numbers through bit operations in C++?
If you need a list of known primes, have a look here
