HashTable

 
/* ============= User Params ============= */
// Note: put a space at the end of these if you're experiencing compiler errors
 
/* Name your class! */
`define CLASS_NAME HashTableV2 
 
/* if this isnt int, turn KEY_CUSTOM on */
`define KEYTYPE IntVector 
 
// If you know your key > 8 bytes, turn this on.
`define PASS_KEY_REFERENCED TRUE
 
// Whether you want to pass keys by reference on user functions such as Add().
`define PASS_KEY_REFERENCED_USER TRUE
 
/* If your key is NOT an int, you will need to write a hashing function for your key type in GetHash(), and turn this on. See below. */
`define KEY_CUSTOM TRUE
 
`define VALUETYPE int 
 
// Whether you want to pass values by reference on the functions Set(), Add() and FindKey().
`define PASS_VALUE_REFERENCED_USER TRUE
 
/* Trades performance for safety. Setting this to false will make validity checks not run on certain user accessible functions. Default is TRUE in editor and FALSE in cooked */
`define SAFE `if(`isdefined(IS_PUBLIC_MODDING_TOOLS)) TRUE `else FALSE `endif
 
/* ============= Non-user macros ============= */
 
// -2147483648 is used for None
`define KEY_NONE `if(`KEY_CUSTOM) class'`CLASS_NAME'.default.DefaultKeyValue `else -2147483648 `endif
`define KEYTYPE_ARG `if(`PASS_KEY_REFERENCED) const out `endif `KEYTYPE
`define KEYTYPE_ARG_USER `if(`PASS_KEY_REFERENCED_USER) const out `endif `KEYTYPE
`define VALUETYPE_ARG_USER `if(`PASS_VALUE_REFERENCED_USER) const out `endif `VALUETYPE
 
// Creates a hash for a pair of two ints. Can be chained.
`define HashPair(A, B) (((`A << 19)|(`A >> 13)) ^ `B)
 
class `CLASS_NAME  extends Object
    hidecategories(Object);
 
struct immutable IntVector extends IntPoint
{
    var() int Z;
 
    structdefaultproperties
    {
        X = -2147483648;
        Y = -2147483648;
        Z = -2147483648;
    }
};
 
struct Pair
{
    var() `KEYTYPE  Key;
    var() `VALUETYPE  Value;
 
    structdefaultproperties
    {
        `if(`KEY_CUSTOM) `else Key = `KEY_NONE `endif
    }
};
 
var private Array<Pair> Data;
var private const float LoadFactor;
var private int TableLength; // Number of real elements
 
`if(`KEY_CUSTOM)
var private const `KEYTYPE DefaultKeyValue;
`endif
 
`if(`KEY_CUSTOM)
// You can write your own hashing function here.
public final function int GetHash(`KEYTYPE_ARG  Key)
{
    return `HashPair(Key.X, `HashPair(Key.Y, Key.Z));
}
`endif
 
/* Add a new key-value pair to the table. */
public function Add(`KEYTYPE_ARG_USER  Key, `VALUETYPE_ARG_USER  Value)
{
    local Pair p;
 
    `if(`SAFE)
    if(Key == `KEY_NONE)
    {
        Print("Cannot use KEY_NONE as a key!");
        return;
    }
 
    if(ContainsKey(Key))
    {
        Print("Key is already in use!");
        return;
    }
    `endif
 
    if(float(TableLength + 1) / float(Data.Length) >= LoadFactor)
    {
        Reserve(Data.Length * 2, true /* bIsBufferLength */);
    }
 
    p.Key = Key;
    p.Value = Value;
 
    Data[GetIndex(Key)] = p;
    TableLength++;
}
 
/* 
Remove a key-value pair from the table, by key. 
bCompact: whether to compact the buffer after removing this element
*/
public function Remove(`KEYTYPE_ARG_USER  Key, optional bool bCompact)
{
    Data[GetIndex(Key)].Key = `KEY_NONE;
    TableLength--;
 
    if(bCompact) Compact();
}
 
/* 
Removes a key-value pair from the table, by key, while providing a copy of the value of the removed pair. 
bCompact: whether to compact the buffer after removing this element.
*/
public function RemoveAndCopyValue(`KEYTYPE_ARG_USER  Key, out `VALUETYPE  Value, optional bool bCompact)
{
    Value = Data[GetIndex(Key)].Value;
    Remove(Key);
 
    if(bCompact) Compact();
}
 
/* Get a value, by key. */
public function `VALUETYPE  Get(`KEYTYPE_ARG_USER  Key)
{
    return Data[GetIndex(Key)].Value;
}
 
/* Set a value, by key. */
public function Set(`KEYTYPE_ARG_USER  Key, `VALUETYPE_ARG_USER  Value)
{
    `if(`SAFE)
    if(!ContainsKey(Key))
    {
        Print("That key isn't used anywhere in the hashtable!");
        return;
    }
    `endif
 
    Data[GetIndex(Key)].Value = Value;
}
 
/* Get the amount of elements in the table */
public function int Length()
{
    return TableLength;
}
 
/* Get the amount of slots in the table */
public function int BufferLength()
{
    return Data.Length;
}
 
/* Check whether the table contains a key. */
public function bool ContainsKey(`KEYTYPE_ARG_USER  Key)
{
    return Data[GetIndex(Key)].Key == Key;
}
 
// Expensive!!
// Finds a key by its associated value.
// Returns `KEY_NONE if no matching value was found
public function `KEYTYPE FindKey(`VALUETYPE_ARG_USER  Value)
{
    local int i;
    for(i = 0; i < Data.Length; i++)
    {
        if(Data[i].Key == `KEY_NONE) continue;
 
        if(Data[i].Value == Value) return Data[i].Key;
    }
    return `KEY_NONE;
}
 
// Expensive!!
// Returns an array of all elements
// Keep in mind that it is not guaranteed for this to be in the order you added the elements in. 
public function Array<Pair> ToArray()
{
    local int i;
    local Array<Pair> Output;
    local Pair p;
 
    for(i = 0; i < Data.Length; i++)
    {
        if(Data[i].Key == `KEY_NONE) continue;
 
        p.Key = Data[i].Key;
        p.Value = Data[i].Value;
        Output.AddItem(p);
    }
 
    return Output;
}
 
/*
Ensure the table atleast has space for x elements without having to resize. 
bIsBufferLength: Nearest prime to NumElements will be directly used as the new length of the buffer, not how many slots are available without resizing. Used internally.
*/
public function Reserve(int NumElements, optional bool bIsBufferLength)
{
    local int MinimumLength;
 
    MinimumLength = bIsBufferLength ? NumElements : FCeil(float(NumElements) * (1.f / LoadFactor));
 
    if(MinimumLength <= Data.Length) return;
 
    UpdateLength(ClosestPrime(MinimumLength));
}
 
/* 
Removes all elements.
Slack: nearest prime to this will indicate how large the buffer will be after removing all elements
*/
public function Empty(optional int Slack = 0)
{
    Data.Length = 0;
    TableLength = 0;
    // Guarantee atleast 2 slots
    Data.Length = 2;
 
    Reserve(Slack, true);
}
 
/* 
Adds another hashtable's contents to this hashtable.
Only identical hashtable types may be appended.
bEmptyTableB: Whether to Empty() TableB after it has been appended. (TRUE by default)
*/
public function Append(`CLASS_NAME  TableB, optional bool bEmptyTableB = true)
{
    local Array<Pair> Elements;
    local int i;
 
    Elements = TableB.ToArray();
 
    Reserve(Length() + Elements.Length);
 
    for(i = 0; i < Elements.Length; i++)
    {
        Add(Elements[i].Key, Elements[i].Value);
    }
 
    if(bEmptyTableB) TableB.Empty();
}
 
/* Shrink the hashtable down to the minimum number of buffer slots before a resize is needed. */
public function Compact()
{
    local int MinimumLength;
 
    MinimumLength = FCeil(float(Length()) * (1.f / LoadFactor));
 
    UpdateLength(ClosestPrime(MinimumLength));
}
 
private function UpdateLength(int NewLength)
{
    local Array<Pair> NewData;
    local int i, k;
    local `KEYTYPE FoundKey;
    k = 1;
    FoundKey = `KEY_NONE;
    NewData.Length = NewLength;
    for(i = 0; i < Data.Length; i++)
    {
        if(Data[i].Key == `KEY_NONE) continue;
 
        k = 1;
 
        // Can't use GetIndex here because its a different buffer so we use this slightly modified version instead
        while(k <= 32)
        {
            FoundKey = NewData[HashPassByValue(Data[i].Key, k) % NewData.Length].Key;
 
            if(FoundKey == `KEY_NONE || FoundKey == Data[i].Key)
            {
                NewData[HashPassByValue(Data[i].Key, k) % NewData.Length] = Data[i];
                break;
            }
 
            k++;
        }
    }
 
    Print("Length updated! ("$String(Data.Length)$" -> "$String(NewLength)$")");
 
    Data = NewData;
}
 
private function int Hash(`KEYTYPE_ARG  Key, int k)
{
    return `if(`KEY_CUSTOM) GetHash(Key) `else Key `endif + k * (1 + (((`if(`KEY_CUSTOM) GetHash(Key) `else Key `endif >> 5) + 1) % (Data.Length - 1)));
}
 
/* Copy of Hash, never passes by reference because of the "not allowed to pass a dynamic array element as the value for an out parameter" rule. Only used in UpdateLength. */
private function int HashPassByValue(`KEYTYPE  Key, int k)
{
    return `if(`KEY_CUSTOM) GetHash(Key) `else Key `endif + k * (1 + (((`if(`KEY_CUSTOM) GetHash(Key) `else Key `endif >> 5) + 1) % (Data.Length - 1)));
}
 
// Handles collisions by rehashing. See above function.
private function int GetIndex(`KEYTYPE_ARG  Key)
{
    local int k;
    local `KEYTYPE FoundKey;
    FoundKey = `KEY_NONE;
    k = 1;
 
    while(k <= 32)
    {
        FoundKey = Data[Hash(Key, k) % Data.Length].Key;
 
        if(FoundKey == `KEY_NONE || FoundKey == Key)
        {
            return Hash(Key, k) % Data.Length;
        }
 
        k++;
    }
}
 
// returns n if n is prime or the next prime if n is composite
// If you've made a faster implementation of this let me know because I'd gladly include it.
private function int ClosestPrime(int n)
{
    local int x;
 
    if(n == 2) return n;
 
    n = n|1; // guarantee n to be odd
 
    x = n;
    while(!IsPrime(x))
        x += 2;
 
    return x;
}
 
// Rabin-miller isnt feasible because of integer overflow, so use trial division instead.
private function bool IsPrime(int n)
{
    local int p, max;
 
    // Skip this because we make it odd in NextPrime().
    //if(n % 2 == 0) return false;
 
    max = Sqrt(n);
 
    // it's already not divisible by 2 so there's no point checking even numbers.
    for(p = 3; p <= max; p += 2)
    {
        if(n % p == 0) return false;
    }
 
    return true;
}
 
`if(`SAFE)
private static final function Print(const string msg)
{
    local WorldInfo wi;
    wi = class'WorldInfo'.static.GetWorldInfo();
    if (wi != None)
    {
        if (wi.GetALocalPlayerController() != None)
            wi.GetALocalPlayerController().TeamMessage(None, msg, 'Event', 6);
        else
            wi.Game.Broadcast(wi, msg);
    }
}
`endif
 
defaultproperties
{
    LoadFactor = 0.72;
    Data.Add(());
    Data.Add(());
}

/* 
A Hashtable stores key-value pairs and provides O(1) lookup time.
⠀
Implementation based on: https://learn.microsoft.com/en-us/previous-versions/ms379571(v=vs.80) (HashTable in C# 2.0)
Some functions are based on TMap<> as it appears in Unreal 4 & 5.
⠀
Value can be made any type by making a copy of this class and search and replacing "ValueType" with the type you want. (and deleting the ValueType dummy struct)
Note: ValueType must have a valid == operator.
After making the copy, replace HashTable types in this class with whatever you called your new class. (This is used for functions such as Append, which take in a HashTable as a parameter.)
⠀
THIS FILE IS A TEMPLATE AND WILL (PROBABLY) NOT COMPILE, SO DO NOT PUT IT IN YOUR CLASSES FOLDER.
*/
class HashTable extends Object;
 
// -2147483648 is used for None
`define KeyNone -2147483648
 
struct ValueType{};
 
struct Pair
{
    var int Key;
    var ValueType Value;
 
    structdefaultproperties
    {
        Key = `KeyNone;
    }
};
 
var private Array<Pair> Data;
var private const float LoadFactor;
var private int TableLength; // Number of elements
var private int LengthIndex; // Index in primes for current buffer length
 
var private const int Primes[303];
 
/* Add a new key-value pair to the table. */
public function Add(int Key, ValueType Value)
{
    local Pair p;
 
    if(Key == `KeyNone)
    {
        Print("Cannot use "$String(`KeyNone)$" as a key!");
        return;
    }
 
    if(ContainsKey(Key))
    {
        Print("Key is already in use!");
        return;
    }
 
    if(float(TableLength + 1) / float(Data.Length) >= LoadFactor)
    {
        Reserve(Data.Length * 2, true /* bIsBufferLength */);
    }
 
    p.Key = Key;
    p.Value = Value;
 
    Data[GetIndex(Key)] = p;
    TableLength++;
}
 
/* 
Remove a key-value pair from the table, by key. 
bCompact: whether to compact the buffer after removing this element
*/
public function Remove(int Key, optional bool bCompact)
{
    Data[GetIndex(Key)].Key = `KeyNone;
    TableLength--;
 
    if(bCompact) Compact();
}
 
/* 
Removes a key-value pair from the table, by key, while providing a copy of the value of the removed pair. 
bCompact: whether to compact the buffer after removing this element.
*/
public function RemoveAndCopyValue(int Key, out ValueType Value, optional bool bCompact)
{
    Value = Data[GetIndex(Key)].Value;
    Remove(Key);
 
    if(bCompact) Compact();
}
 
/* Get a value, by key. */
public function ValueType Get(int Key)
{
    return Data[GetIndex(Key)].Value;
}
 
/* Set a value, by key. */
public function Set(int Key, ValueType Value)
{
    if(!ContainsKey(Key))
    {
        Print("That key isn't used anywhere in the hashtable!");
        return;
    }
 
    Data[GetIndex(Key)].Value = Value;
}
 
/* Get the amount of elements in the table */
public function int Length()
{
    return TableLength;
}
 
/* Get the amount of slots in the table */
public function int BufferLength()
{
    return Primes[LengthIndex];
}
 
/* Check whether the table contains a key. */
public function bool ContainsKey(int Key)
{
    return Data[GetIndex(Key)].Key == Key;
}
 
// Expensive!!
// Finds a key by its associated value.
// Returns `KeyNone if no matching value was found
public function int FindKey(ValueType Value)
{
    local int i;
    for(i = 0; i < Data.Length; i++)
    {
        if(Data[i].Key == `KeyNone) continue;
 
        if(Data[i].Value == Value) return Data[i].Key;
    }
    return `KeyNone;
}
 
// Expensive!!
// Returns an array of all elements
// Keep in mind that it is not guaranteed for this to be in the order you added the elements in. 
public function Array<Pair> ToArray()
{
    local int i;
    local Array<Pair> Output;
    local Pair p;
 
    for(i = 0; i < Data.Length; i++)
    {
        if(Data[i].Key == `KeyNone) continue;
 
        p.Key = Data[i].Key;
        p.Value = Data[i].Value;
        Output.AddItem(p);
    }
 
    return Output;
}
 
/*
Ensure the table atleast has space for x elements without having to resize. 
bIsBufferLength: Nearest prime to NumElements will be directly used as the new length of the buffer, not how many slots are available without resizing. Used internally.
*/
public function Reserve(int NumElements, optional bool bIsBufferLength)
{
    local int MinimumLength, i;
 
    MinimumLength = FCeil(float(NumElements) * (1.f / LoadFactor));
 
    if(MinimumLength <= Data.Length) return;
 
    for(i = LengthIndex; i < ArrayCount(Primes); i++)
    {
        if(Primes[i] >= (bIsBufferLength ? NumElements : MinimumLength))
        {
            UpdateLength(Primes[i]);
            LengthIndex = i;
            return;
        }
    }
 
    Print("Failed to accommodate wanted number of elements ("$String(NumElements)$")!");
}
 
/* 
Removes all elements.
Slack: nearest prime to this will indicate how large the buffer will be after removing all elements
*/
public function Empty(optional int Slack = 0)
{
    Data.Length = 0;
    TableLength = 0;
    LengthIndex = 0;
    // Guarantee atleast 2 slots
    Data.Length = Primes[0];
 
    Reserve(Slack, true);
}
 
/* 
Adds another hashtable's contents to this hashtable.
Only identical hashtable types may be appended.
bEmptyTableB: Whether to Empty() TableB after it has been appended. (TRUE by default)
*/
public function Append(HashTable TableB, optional bool bEmptyTableB = true)
{
    local Array<Pair> Elements;
    local int i;
 
    Elements = TableB.ToArray();
 
    Reserve(Length() + Elements.Length);
 
    for(i = 0; i < Elements.Length; i++)
    {
        Add(Elements[i].Key, Elements[i].Value);
    }
 
    if(bEmptyTableB) TableB.Empty();
}
 
/* Shrink the hashtable down to the minimum number of buffer slots before a resize is needed. */
public function Compact()
{
    local int MinimumLength, i;
    MinimumLength = FCeil(float(Length()) * (1.f / LoadFactor));
 
    for(i = 0; i < arraycount(Primes); i++)
    {
        if(Primes[i] >= MinimumLength)
        {
            UpdateLength(Primes[i]);
            LengthIndex = i;
            return;
        }
    }
 
}
 
private function UpdateLength(int NewLength)
{
    local Array<Pair> NewData;
    local int i, FoundKey, k;
    k = 1;
    FoundKey = `KeyNone;
    NewData.Length = NewLength;
    for(i = 0; i < Data.Length; i++)
    {
        if(Data[i].Key == `KeyNone) continue;
 
        k = 1;
 
        // Can't use GetIndex here because its a different buffer so we use this slightly modified version instead
        while(k <= 32)
        {
            FoundKey = NewData[Hash(Data[i].Key, k) % NewData.Length].Key;
 
            if(FoundKey == `KeyNone || FoundKey == Data[i].Key)
            {
                NewData[Hash(Data[i].Key, k) % NewData.Length] = Data[i];
                break;
            }
 
            k++;
        }
    }
 
    Print("Length updated! ("$String(Data.Length)$" -> "$String(NewLength)$")");
 
    Data = NewData;
}
 
private function int Hash(int Key, int k)
{
    return Key + k * (1 + (((Key >> 5) + 1) % (Data.Length - 1)));
}
 
// Handles collisions by rehashing. See above function.
private function int GetIndex(int Key)
{
    local int FoundKey, k;
    FoundKey = `KeyNone;
    k = 1;
 
    while(k <= 32)
    {
        FoundKey = Data[Hash(Key, k) % Data.Length].Key;
 
        if(FoundKey == `KeyNone || FoundKey == Key)
        {
            return Hash(Key, k) % Data.Length;
        }
 
        k++;
    }
}
 
private static final function Print(const string msg)
{
    local WorldInfo wi;
    wi = class'WorldInfo'.static.GetWorldInfo();
    if (wi != None)
    {
        if (wi.GetALocalPlayerController() != None)
            wi.GetALocalPlayerController().TeamMessage(None, msg, 'Event', 6);
        else
            wi.Game.Broadcast(wi, msg);
    }
}
 
defaultproperties
{
    LoadFactor = 0.72;
    Data.Add(());
    Data.Add(());
    LengthIndex = 0;
 
    Primes[0] = 2;
    Primes[1] = 3;
    Primes[2] = 5;
    Primes[3] = 7;
    Primes[4] = 11;
    Primes[5] = 13;
    Primes[6] = 17;
    Primes[7] = 19;
    Primes[8] = 23;
    Primes[9] = 29;
    Primes[10] = 31;
    Primes[11] = 37;
    Primes[12] = 41;
    Primes[13] = 43;
    Primes[14] = 47;
    Primes[15] = 53;
    Primes[16] = 59;
    Primes[17] = 61;
    Primes[18] = 67;
    Primes[19] = 71;
    Primes[20] = 73;
    Primes[21] = 79;
    Primes[22] = 83;
    Primes[23] = 89;
    Primes[24] = 97;
    Primes[25] = 101;
    Primes[26] = 103;
    Primes[27] = 107;
    Primes[28] = 109;
    Primes[29] = 113;
    Primes[30] = 127;
    Primes[31] = 131;
    Primes[32] = 137;
    Primes[33] = 139;
    Primes[34] = 149;
    Primes[35] = 151;
    Primes[36] = 157;
    Primes[37] = 163;
    Primes[38] = 167;
    Primes[39] = 173;
    Primes[40] = 179;
    Primes[41] = 181;
    Primes[42] = 191;
    Primes[43] = 193;
    Primes[44] = 197;
    Primes[45] = 199;
    Primes[46] = 211;
    Primes[47] = 223;
    Primes[48] = 227;
    Primes[49] = 229;
    Primes[50] = 233;
    Primes[51] = 239;
    Primes[52] = 241;
    Primes[53] = 251;
    Primes[54] = 257;
    Primes[55] = 263;
    Primes[56] = 269;
    Primes[57] = 271;
    Primes[58] = 277;
    Primes[59] = 281;
    Primes[60] = 283;
    Primes[61] = 293;
    Primes[62] = 307;
    Primes[63] = 311;
    Primes[64] = 313;
    Primes[65] = 317;
    Primes[66] = 331;
    Primes[67] = 337;
    Primes[68] = 347;
    Primes[69] = 349;
    Primes[70] = 353;
    Primes[71] = 359;
    Primes[72] = 367;
    Primes[73] = 373;
    Primes[74] = 379;
    Primes[75] = 383;
    Primes[76] = 389;
    Primes[77] = 397;
    Primes[78] = 401;
    Primes[79] = 409;
    Primes[80] = 419;
    Primes[81] = 421;
    Primes[82] = 431;
    Primes[83] = 433;
    Primes[84] = 439;
    Primes[85] = 443;
    Primes[86] = 449;
    Primes[87] = 457;
    Primes[88] = 461;
    Primes[89] = 463;
    Primes[90] = 467;
    Primes[91] = 479;
    Primes[92] = 487;
    Primes[93] = 491;
    Primes[94] = 499;
    Primes[95] = 503;
    Primes[96] = 509;
    Primes[97] = 521;
    Primes[98] = 523;
    Primes[99] = 541;
    Primes[100] = 547;
    Primes[101] = 557;
    Primes[102] = 563;
    Primes[103] = 569;
    Primes[104] = 571;
    Primes[105] = 577;
    Primes[106] = 587;
    Primes[107] = 593;
    Primes[108] = 599;
    Primes[109] = 601;
    Primes[110] = 607;
    Primes[111] = 613;
    Primes[112] = 617;
    Primes[113] = 619;
    Primes[114] = 631;
    Primes[115] = 641;
    Primes[116] = 643;
    Primes[117] = 647;
    Primes[118] = 653;
    Primes[119] = 659;
    Primes[120] = 661;
    Primes[121] = 673;
    Primes[122] = 677;
    Primes[123] = 683;
    Primes[124] = 691;
    Primes[125] = 701;
    Primes[126] = 709;
    Primes[127] = 719;
    Primes[128] = 727;
    Primes[129] = 733;
    Primes[130] = 739;
    Primes[131] = 743;
    Primes[132] = 751;
    Primes[133] = 757;
    Primes[134] = 761;
    Primes[135] = 769;
    Primes[136] = 773;
    Primes[137] = 787;
    Primes[138] = 797;
    Primes[139] = 809;
    Primes[140] = 811;
    Primes[141] = 821;
    Primes[142] = 823;
    Primes[143] = 827;
    Primes[144] = 829;
    Primes[145] = 839;
    Primes[146] = 853;
    Primes[147] = 857;
    Primes[148] = 859;
    Primes[149] = 863;
    Primes[150] = 877;
    Primes[151] = 881;
    Primes[152] = 883;
    Primes[153] = 887;
    Primes[154] = 907;
    Primes[155] = 911;
    Primes[156] = 919;
    Primes[157] = 929;
    Primes[158] = 937;
    Primes[159] = 941;
    Primes[160] = 947;
    Primes[161] = 953;
    Primes[162] = 967;
    Primes[163] = 971;
    Primes[164] = 977;
    Primes[165] = 983;
    Primes[166] = 991;
    Primes[167] = 997;
    Primes[168] = 1009;
    Primes[169] = 1013;
    Primes[170] = 1019;
    Primes[171] = 1021;
    Primes[172] = 1031;
    Primes[173] = 1033;
    Primes[174] = 1039;
    Primes[175] = 1049;
    Primes[176] = 1051;
    Primes[177] = 1061;
    Primes[178] = 1063;
    Primes[179] = 1069;
    Primes[180] = 1087;
    Primes[181] = 1091;
    Primes[182] = 1093;
    Primes[183] = 1097;
    Primes[184] = 1103;
    Primes[185] = 1109;
    Primes[186] = 1117;
    Primes[187] = 1123;
    Primes[188] = 1129;
    Primes[189] = 1151;
    Primes[190] = 1153;
    Primes[191] = 1163;
    Primes[192] = 1171;
    Primes[193] = 1181;
    Primes[194] = 1187;
    Primes[195] = 1193;
    Primes[196] = 1201;
    Primes[197] = 1213;
    Primes[198] = 1217;
    Primes[199] = 1223;
    Primes[200] = 1229;
    Primes[201] = 1231;
    Primes[202] = 1237;
    Primes[203] = 1249;
    Primes[204] = 1259;
    Primes[205] = 1277;
    Primes[206] = 1279;
    Primes[207] = 1283;
    Primes[208] = 1289;
    Primes[209] = 1291;
    Primes[210] = 1297;
    Primes[211] = 1301;
    Primes[212] = 1303;
    Primes[213] = 1307;
    Primes[214] = 1319;
    Primes[215] = 1321;
    Primes[216] = 1327;
    Primes[217] = 1361;
    Primes[218] = 1367;
    Primes[219] = 1373;
    Primes[220] = 1381;
    Primes[221] = 1399;
    Primes[222] = 1409;
    Primes[223] = 1423;
    Primes[224] = 1427;
    Primes[225] = 1429;
    Primes[226] = 1433;
    Primes[227] = 1439;
    Primes[228] = 1447;
    Primes[229] = 1451;
    Primes[230] = 1453;
    Primes[231] = 1459;
    Primes[232] = 1471;
    Primes[233] = 1481;
    Primes[234] = 1483;
    Primes[235] = 1487;
    Primes[236] = 1489;
    Primes[237] = 1493;
    Primes[238] = 1499;
    Primes[239] = 1511;
    Primes[240] = 1523;
    Primes[241] = 1531;
    Primes[242] = 1543;
    Primes[243] = 1549;
    Primes[244] = 1553;
    Primes[245] = 1559;
    Primes[246] = 1567;
    Primes[247] = 1571;
    Primes[248] = 1579;
    Primes[249] = 1583;
    Primes[250] = 1597;
    Primes[251] = 1601;
    Primes[252] = 1607;
    Primes[253] = 1609;
    Primes[254] = 1613;
    Primes[255] = 1619;
    Primes[256] = 1621;
    Primes[257] = 1627;
    Primes[258] = 1637;
    Primes[259] = 1657;
    Primes[260] = 1663;
    Primes[261] = 1667;
    Primes[262] = 1669;
    Primes[263] = 1693;
    Primes[264] = 1697;
    Primes[265] = 1699;
    Primes[266] = 1709;
    Primes[267] = 1721;
    Primes[268] = 1723;
    Primes[269] = 1733;
    Primes[270] = 1741;
    Primes[271] = 1747;
    Primes[272] = 1753;
    Primes[273] = 1759;
    Primes[274] = 1777;
    Primes[275] = 1783;
    Primes[276] = 1787;
    Primes[277] = 1789;
    Primes[278] = 1801;
    Primes[279] = 1811;
    Primes[280] = 1823;
    Primes[281] = 1831;
    Primes[282] = 1847;
    Primes[283] = 1861;
    Primes[284] = 1867;
    Primes[285] = 1871;
    Primes[286] = 1873;
    Primes[287] = 1877;
    Primes[288] = 1879;
    Primes[289] = 1889;
    Primes[290] = 1901;
    Primes[291] = 1907;
    Primes[292] = 1913;
    Primes[293] = 1931;
    Primes[294] = 1933;
    Primes[295] = 1949;
    Primes[296] = 1951;
    Primes[297] = 1973;
    Primes[298] = 1979;
    Primes[299] = 1987;
    Primes[300] = 1993;
    Primes[301] = 1997;
    Primes[302] = 1999;
}