Practical number algorithm

I am trying to write a program to find the practical numbers, from an input from \$1\$ to \$n\$.

Practical numbers

My code is running correctly but it is extremely slow when calculating numbers around 50 - it gets stuck at 44.

``
import Foundation

func getInteger() -> Int {
var firstNum:Int = 0
while true {
// get value from user. Using optional input since readLine returns an optional string.
let input = readLine()
// ensure string is not nil
if let unwrappedInput = input {
if let unwrappedInt = Int(unwrappedInput) {
firstNum = unwrappedInt
break
}
else { // the input doesn't convert into an int
print("\(unwrappedInput)` is not an integer. Please enter an integer")
}
}
else { // did not enter anything
print("Please enter an integer")
}
}

return firstNum
}
func addOne(signArray: [Int]) -> [Int] { // finds the combinations
var signArray2 = [Int]()
for i in 0...signArray.count-1 {
signArray2.append (signArray[i])
}

for i in 0...signArray2.count-1 {
if signArray2[i] == 1 {
signArray2[i] = 0
}
else {
signArray2[i] = 1
break
}
}
return signArray2
}
func signEval (signArray: [Int], divArray: [Int], inNum: Int) -> Bool {// changes 2nd
var counts = 0
for i in 0...divArray.count-1 {
if signArray[i] == 0 {
counts = divArray[i] + counts }
if counts == inNum {
return true
}
}
return false
}
print("Please enter a number to find the summable numbers up to that number:")
var input2 = getInteger()// if num = 1 print 1 if num = 2 print 1 and 2 else print >2 1, 2
var inNum = 0
var numHalf = 0.0
var numRound = 0.0
var numCheck = false
var numCheck2 = false
var numQuarter = 0.0
var numSixth = 0.0
var divArray:[Int] = []
var theirArray = [Int]

Some points in addition to what Roland already said:

You are correct that the readLine() returns an optional and you need
to ensure that it is not nil. However, nil is only returned on an
end-of-file condition, which means that it makes no sense to call
readLine() again. You can only terminate the program in that
situation. That is a typical use-case for guard:

func readInteger() -> Int {
    while true {
        guard let line = readLine() else {
            fatalError("Unexpected end-of-file")
        }
        if let n = Int(line) {
            return n
        }
        print("Please enter an integer")
    }
}

Now let's have a look at

var signArray2 = [Int]()
for i in 0...signArray.count-1 {
    signArray2.append (signArray[i])
}

First, this will crash if signArray is empty. Better use a half-open
range instead:

for i in 0..<signArray.count { ... }

or iterate over the indices

for i in signArray.indices {
    signArray2.append (signArray[i])
}

or just iterate over the elements:

for e in signArray {
    signArray2.append(e)
}

But actually, you are just copying the array:

var signArray2  = signArray

Determination of the divisors should be done in a separate function.
Your code

divArray = []
for i in 1...input {
    if input % i == 0 {
        divArray.append (i)
    }
}

can be simplified to

divArray = (1...input).filter { input % $0 == 0 }

There are various ways to make this faster. For example the observation
that with each divisor \$ i \$ of a number \$ n \$, \$ n/i \$ is another
divisor (see for example Find all divisors of a natural number).
That allows to reduce the number of loop iterations to the square-root of the
given number, and could look like this:

func divisors(n: Int) -> [Int] {
    var divs = [Int]()
    for i in 1...Int(sqrt(Double(n))) {
        if n % i == 0 {
            divs.append(i)
            if n/i != i {
                divs.append(n/i)
            }
        }
    }
    return divs // or divs.sorted(), if necessary
}

Your code

signArray = []
for j in 1...divArray.count {//
    signArray.append(0)
}

creates an array with the same size as divArray, but filled with
zeros. That can be simplified to

signArray = Array(repeating: 0, count: divArray.count)

There is no need to use string interpolation when printing an integer
(or any single value),

print ("\(input)")

can be simplified to

print(input)

Why is your code slow?

There is a logical error in

let x: Int = Int(pow(Double(2),Double(input-1)))// int 2 to the power of input -1

because the number of possible combinations of divisors is
just \$ 2 ^ {\text{number of divisors}} \$, which can be computed as

let x = 1 << divArray.count

With that change, your program computes all practical numbers
up to 200 in 0.2 seconds, and up to 1,000 in 25 seconds
(on a MacBook, compiled in Release mode, with optimization).

A faster algorithm

In order to determine if \$ n \$ is a practical number,
you test all numbers \$ 1 \le i \le n \$ if they are a sum
of distinct divisors of \$ n \$, and for each \$ i \$ that is done by building all
possible sums of divisors, until \$ i \$ is found.

It is more efficient to work the other way around. From the list of
divisors of \$ n \$, build a list of all sums of distinct divisors.
This can be done iteratively: Starting with \$ 0 \$, the first, second, ...
divisor is added to the numbers obtained previously.
Then check if all numbers from \$ 1 ... n-1 \$ are in that list.

The following implementation uses a boolean array to mark all numbers
which are confirmed as sums of divisors. In addition, it uses that
powers of two are always practical numbers (using the method from
Determining if an integer is a power of 2).

``
func divisors(_ n: Int) -> [Int] {
var divs = [Int]()
for i in 1...Int(sqrt(Double(n))) {
if n % i == 0 {
divs.append(i)
if n/i != i {
divs.append(n/i)
}
}
}
return divs.sorted()
}

func isPractical(n: Int) -> Bool {
// 1 and 2 are practical numbers:
if n == 1 || n == 2 {
return true
}
// Every other practical number must be divisible by 4 or 6:
if n % 4 != 0 && n % 6 != 0 {
return false
}
// Every power of 2 is a practical number:
if n & (n-1) == 0 {
return true
}

var isSumOfDivisors = Array(repeating: false, count: n)
isSumOfDivisors[0] = true
var last = 0 // Index of last true` element.

// For all divisors d of n (except n):
for d in divisors(n).dropLast() {
// For all i which are a sum of smaller divisors (in reverse order, so that
// we can simply update the array):
for i in stride(from: min(last, n-1-d), through: 0, by: -1) where isSumOfDivisors[i] {
// Mark i + d:
isSumOfDivisors[i + d] = true
if i

StackExchange Code Review Q#158142, answer score: 4