/* Created for challenge by Nevfy https://www.sololearn.com/Discuss/1207798 [ASSIGNMENT] Super Prime Numbers The number X is called Super Prime if it is Prime and can be represented as: X = 2^n+3^m, where n,m - non-negative integers Task 1: Write a function isSuperPrime(X) which checks X and returns True or False NOTE: Brut-force solution is acceptable, but not the best one. Task 2: Print out all Super Prime numbers from a given range [A,B] NOTE: Solution, which checks one by one numbers from range [A,B] using a function from task 1, is acceptable BUT not optimal. I highly recommend to find a better one! */ //************************************************** // Extend Int to add raise to power. Keeping track of // the ones we have seen before as we are repeatably // getting powers of 2 and 3. Store the 0 power into // the list to start us off. var power = MutableList(2, {_ -> MutableList(1, {_ -> 1})}) fun Int.pow(number: Int): Int = if (power[this-2].size > number) power[this-2][number] else { val result = this.pow(number-1)*this power[this-2].add(result) result } // if //************************************************** // Figure out top end power and setup the array. fun Int.setupPow(number: Int) { var value = number var power = 0 while (value > 0) { power++ value /= this } // while this.pow(power) } // setupPow //************************************************** // Single node template of the linked list storing // a value of whatever type, a pointer to the // previous node, and a pointer to the next node. data class Node(var value: T, var previous: Node? = null, var next: Node? = null) //************************************************** // Class providing a first in first out template for // a linked list. open class List() { // Pointers to the head and tail of the list plus // size of list. protected var head: Node? = null protected var tail: Node? = null var size: Int = 0 protected set //------------------------------------------------ // Create an interator over the list. operator open fun iterator(): Iterator = ListIterator(this, 0, size-1) //------------------------------------------------ // Provide this[index] to get read access to the // value within the node in that position. Head // points at index of zero. operator fun get(index: Int): T { // Find the node by starting with the head // node and copy of the index. While there // is another node and we haven't found the // right one, decrement the position and move // down the list. Return null or the node's // value. var node = head var position = index while (node != null && position != 0) { position -= 1 node = node.next } // while return node!!.value } // get //------------------------------------------------ // Provide this[index] to get write access to the // value within the node in that position. Head // points at index of zero. operator fun set(index: Int, value: T) { // If we have a valid index, find the node. // Start with the head node and copy of the // index. While there is another node and we // haven't found the right one, decrement the // position and move down the list. if (index >= 0) { var node = head var position = index while (node != null && position != 0) { position -= 1 node = node.next } // while // If we have found the node, update it's // value. if (node != null) node.value = value; } // if } // set //------------------------------------------------ // Push a new value on to the tail of the list. fun push(value: T) { // Allocate the new node with the passed in value. // If the head is null, make it point to the new // node. val newNode = Node(value) if (tail == null) head = newNode // Otherwise, make the current last node point to // the new node and the new node point back at it. else { tail?.next = newNode newNode.previous = tail } // if // The tail must point to the new node in either // case and increment the size. tail = newNode size++ } // push //------------------------------------------------ // Pop the first value off the list. fun pop(): T? = // If the head is null, return it. if (head == null) null // Otherwise, decrement the size, grab the // first node, make next node the new head, // make it's previous null, make the first // node's next pointer null, and return the // value. Note: testing for null shouldn't // be needed, but head might be changed // asynchronously so it is required. else { size-- val node = head head = head?.next head?.previous = null node?.next = null node?.value } // if //------------------------------------------------ // This function is called by default to print this // class so make a list of the values in the list. // An integer list will look like: [1, 2, 3]. override fun toString(): String { // Start the finished string with the open // bracket and process the list. var s = "[" var node = head while (node != null) { // Add the current node's value to the string, // move on the next node, and, if there is one, // add the comma to the string. s += "${node.value}" node = node.next if (node != null) s += ", " } // while // Return the finished string with the close // bracket. return s+"]" } // toString } // List //************************************************** // Create an iterator class allocating the list and // the current & end positions. class ListIterator(private val self: List, start: Int, private val end: Int): Iterator { private var current = start //------------------------------------------------ // Test to see if any more elements exist. override fun hasNext(): Boolean = current <= end //------------------------------------------------ // Return the value of the current element // incrementing to the next one. override fun next(): T = self[current++] } // ListIterator //************************************************** // Override the iterator and add a new method. class Primes: List() { //------------------------------------------------ // Create an interator over the list. operator override fun iterator(): Iterator = PrimesIterator(this) //------------------------------------------------ // Return the value of the last node. fun last(): Int = tail!!.value } // Primes //************************************************** // Create an iterator class to figure out the next // prime number so there is an infinite supply. class PrimesIterator(private val self: Primes): Iterator { //------------------------------------------------ // There is always another prime. override fun hasNext(): Boolean = true //------------------------------------------------ // Figure out the next prime adding it to our list. override fun next(): Int = // If our list is empty, our first is 2. if (self.size == 0) { self.push(2) 2 // Otherwise, if we returned 2, our second is 3. } else if (self.size == 1) { self.push(3) 3 // Otherwise, we can now find it by processing // our last one so do it. } else { // Take the last prime found and start at the // next odd number looping until a new one // is found. var number = self.last()+2 outer@ while (true) { // For each of the primes found so far, if // it divides evenly into the number, the // number can't be a prime so skip checking // the others. Otherwise, if the prime is // too big to be the smallest factor of the // number, the number must be a prime. // Otherwise, continue processing the next // prime. for (index in 0 until self.size) { val factor = self[index] if (number%factor == 0) break else if (factor*factor > number) break@outer } // for number += 2 } // while // No factor was found so add the prime to our // list and return it. self.push(number) number } // if } // PrimesIterator //************************************************** // Decide if a number is a prime. var primes = Primes() fun isPrime(number: Int): Boolean { var result = false for (factor in primes) if (number%factor == 0) break else if (factor*factor > number) { result = true break } // if return result } // isPrime //************************************************** // Decide if the number is a super prime. fun isSuperPrime(number: Int, prime: Boolean): Boolean { // Default to not a super prime and if the number // is prime, check it. var result = false if (prime || isPrime(number)) { // Start looping with maximum power of 2 giving up // when the power of 2 is negative. Declare power // of 3. var two = power[0].size-1 var three = 0 outer@ do { var twos = power[0][two] // Start looping with maximum power of 3 // giving up when the power of 3 is negative. three = power[1].size-1 do { var threes = power[1][three] // If this combination of powers of 2 and 3 // equal the number, it is a super prime so // note that and exit both loops. if (twos+threes == number) { result = true break@outer } // if // Get the next power of 3. three-- } while (three >= 0) // Get the next power of 2. two-- } while (two >= 0) // If it's a super prime, state how. if (result) println( "$number is a super prime 2^$two+3^$three.") // Otherwise, it a regular prime so state that. else println("$number is prime, but not super.") // Otherwise, the isn't prime so state that. } else println("$number is not prime.") return result } // isSuperPrime //************************************************** // Get inputs and verify super primes. fun main(args: Array) { // Default the input values before trying to // read them. var value = 0 var start = 0 var end = 0 try { // Read the input values. If only one value, // convert it to a single value to process. val numbers = readLine()!!.split(" ") if (numbers.size == 1) value = numbers[0].toInt() // Otherwise, convert both values to a range. else { start = numbers[0].toInt() end = numbers[1].toInt() } // if // Otherwise, catch whatever error has occurred // and default the value. } catch (error: Throwable) { value = 29 println("Error, defaulting to $value.") // Otherwise, verify the data and process it. } finally { // If we got a range, verify it. if (value == 0) { // If the range is starting too low, default // it and display the error message. if (start < 2) { start = 2 println( "Invalid start, defaulting to $start.") } // if // If the range is ending too low, default // it to a single value and display the // error message. if (end < start) { value = start println("Invalid end, defaulting to $start.") } // if // Otherwise, we only got a single number so // make sure it isn't too low. If it is too low, // default it and display the error message. } else if (value < 2) { value = 2 println("Invalid number, defaulting to $value.") } // if // If we only want one value, initialize the // power array and process the value. if (value != 0) { 2.setupPow(value) 3.setupPow(value) isSuperPrime(value, false) // Otherwise, we want a range so process them. } else { // Initialize the power array. 2.setupPow(end) 3.setupPow(end) // For all primes, skip them until within the // range. Note if we had a prime in the range // and check if it is a super prime. var found = false for (number in primes) if (number > end) break else if (number >= start) { found = true isSuperPrime(number, true) } // if // If no primes in the range, state that. if (!found) println("No primes within range.") } // if } // try } // main

superPrime ch