# Prime numbers in Scheme

Page 1 of 1

## 4 Replies - 6646 Views - Last Post: 27 November 2011 - 11:26 PM

### #1 leakk

Reputation: 0
• Posts: 1
• Joined: 15-November 11

# Prime numbers in Scheme

Posted 15 November 2011 - 08:26 AM

Okay guys, I'm trying to do a program that checks if a given number is prime or not.

So far what I got:

- Even numbers are not prime so I need check if a given number is even or not;
- If it is, I give "#f", if it isn't I need to divide it by 2, if the remainder is 0 I give "#f", if it's not 0 I divide it by the 3,..., until sqrt N where N is the given number.

I'm not getting how I will pass that to the language itself...

Can I do it recursively?

I think I need to create a new variable that will add one everytime the remainder isn't 0...

Would be glad if someone could help me.

Is This A Good Question/Topic? 0

## Replies To: Prime numbers in Scheme

### #2 jon.kiparsky

• Pancakes!

Reputation: 8933
• Posts: 15,439
• Joined: 19-March 11

## Re: Prime numbers in Scheme

Posted 17 November 2011 - 02:58 PM

You can do this recursively if you want.

Define a function of two arguments, the number to test and the divisor to try.

If the divisor is greater than the largest number you need to try (which is?) then return true: you've tried all of the possible divisors, so it must be prime.
If the divisor divides the test number evenly, return false, obviously
Otherwise, return the result of this function with the same number, and the next divisor you want to try.

Which is the next divisor? Well, just increment the divisor first. We can talk about optimizing it once you have it working. For now, just test every number up to... what? (since you're doing this in a loop, you want to test as few numbers as possible... what's the lowest number you need to test?)

### #3 ishkabible

• spelling expret

Reputation: 1676
• Posts: 5,836
• Joined: 03-August 09

## Re: Prime numbers in Scheme

Posted 27 November 2011 - 01:22 PM

sooo... sense this doesn't seem to be going anywhere, mind if i jack this thread?

i decided to try scheme and give this problem a try for my self after reading a bit. i would love to have someone review though

```(define prime?                         ;define global
(lambda (x)
(letrec ((is-prime?                ;declare local that can call itself
(lambda (x n)
(if (= (remainder x n) 0)      ;divisable by current n?
#f                           ;not prime
(or                          ;checked enoghe or check again?
(> n (sqrt x))             ;checked engohe
(is-prime? x (+ n 1))))))) ;check again
(case x                          ;handle exceptions to algorthim
((0) #f)                       ;numbers that is-prime? breaks on
((1) #f)
((2) #t)
(else (is-prime? x 2))))))     ;check from 2 to (sqrt x)

(define (main args)
(begin
(newline)))
```

### #4 jon.kiparsky

• Pancakes!

Reputation: 8933
• Posts: 15,439
• Joined: 19-March 11

## Re: Prime numbers in Scheme

Posted 27 November 2011 - 01:40 PM

Looks like it should work. It looks a little busy for me, though. You're repeating a lot of work.
If you've already determined that a number is prime, you should remember that, so you don't need to calculate that again. And of course, the only potential divisors that you need to worry about are the primes, so if you have a list, you're much more than halfway there.

So I would suggest you define a list of primes, and a "max-checked", which just stores the top end of the range that you've examined. If the number you're checking (n) is less than max-checked, just look to see if it's on the list. If it's greater than max-checked, you might as well check the range between max-checked and n - you'll have to look at those in any case, so you might as well remember them.

Suppose I have (2, 3, 5, 7, 11, 13), and max-checked is 15, and you ask me about 17. I'm going to look at 16 - (% 16 2) = 0, so I don't add it to the list. (% 17 2) = 1, (% 17 3) = 2, and 5 is greater than (sqrt 17), so I'm done, and I add 17 and set max-checked to 17.

Now you ask me about 12 - it's less than 17, so I look down the list, and 12 isn't on it, so I'm done.

Makes sense?

### #5 ishkabible

• spelling expret

Reputation: 1676
• Posts: 5,836
• Joined: 03-August 09

## Re: Prime numbers in Scheme

Posted 27 November 2011 - 11:26 PM

i was more concerned with the style, it seems like a lot of messy code to do something so simple(and with no optmizations!) in a language that is herald as being elegant and expressive. a Haskell implementation i made a while back is much shorter and about 25% of that code is handling typing. i feel that someone with more experience could make something just as good with much less effort.