C# beginner

OK, first semester in C# and just starting to work on it.  Haven't programmed in a long time, kinda stumped on this one.  The assignment is to determine if a number is prime, and if its not, to factor it.  I know what a prime number is in my head, but I don't really know how to put that into code.

Thanks.

sub is_prime{map{$n*=$n%$_>0}2..($n=pop)/2;$n>1}

>>1
That's what your assignment is about, to know how to write that in code. I'll lend you a hand, which is much better for you than if I write it.

To know if a number is prime, you could try dividing it by anything - anything it should be divided by, that is. You wouldn't divide by 0 unless you're in /sci, you won't divide by 1 because it'll always work, so you want to start with 2. And where will you end? To check for primality, you'd end in the square root of the number. For example, for 100, you'd try 2 to 10. Of course, there are divisors higher than 10, like 20, but what's 100/20? 5 - you'd catch this one earlier on anyways.

So you should take the number, and loop from 2 to the square root of that number, trying to divide the number and seeing if it can be divided. How? When you can divide A by B (integer division), A mod B (A % B) is 0.

Then onto factoring. Think of how you do it by hand.


#!/usr/bin/perl -l

sub is_prime{my$n;map{$n*=$n%$_>0}2..($n=pop)**.5;$n>1}
sub factor{my$n,@f;map{until($n%$_){push@f,$_;$n/=$_}}2..($n=pop)/2;@f}

my$n=pop;
print is_prime($n)?"$n is prime.":"factors of $n: ".join',',factor$n

>>4

sub is_prime{$_='x'x pop;/../^/^(..+)\1+$/}
sub factor{my$n=pop;map{($n/=$_,push@_,$_)until$n%$_}2..$n;@_}

(defun primep (number)
  (when (> number 1)
    (loop for fac from 2 to (isqrt number) never (zerop (mod number fac)))))

(defun next-prime (number)
  (loop for n from number when (primep n) return n))

(defmacro do-primes (var-and-range &rest body)
  (let ((var (first var-and-range))
        (start (second var-and-range))
        (end (third var-and-range)))
    `(do ((,var (next-prime ,start) (next-prime (1+ ,var))))
         ((> ,var ,end))
       ,@body)))

>>6
Thanks for refreshing my mind on why shouldn't I learn Lisp. Lisp is the Perl of functional programming.

>>1
pseudocode:
IS-PRIME(N)
    if N ends in a 3, 5 or 7
        yeah
    else
        nah
sorry it's kind of hand wavy, I'm a researcher lulz

>>8
Wrong.  11 is prime and your function fails to think so.

>>7
More like the Java, it's so damned verbose.

>>10
It's verbose, but I'm not that worried about it as I'm worried about being cryptic and made of punctuation.

I said it's the Perl of FP because Perl is //()/$(=)/"&"#&%#?"()%/ and LISP is (((((()))))))))())))))))()()))))))))))))()))))((((())))))))))))))))))))) which is just as ugly.

erm primality testing is a very hard question. there are no efficient algorithms for it atm.

>>12
Since we're handling ints, we can safely use Fermat's theorem and check for all Carmichael numbers in the int range.

>>12
Try using a lookup table for like the first 1000 primes, and calculate from there other primes that are bigger.

>>11
that's the stupidest "lisp" example I've ever seen, and it's not even Lisp at all...

>>12-14
this is probably efficient enough for most purposes...
may require some changes to work in your shitty language...

#include <math.h>
int is_prime(int n){for(int i=2;i<=sqrt(n);++i)n=n%i?n:0;return n>1;}

>>16
No one said it wasn't except for >>12.

>>15
Boy, you sure are easy to troll, even when I was not trolling. $(/()()="%/)="$&#"$/& is not Perl either (it may even be, but it's not intended to). I'm just describing how Perl  ( /(%)/="#$(/"=#()$/$ ) and LISP ( ((((())))))))()()()))()(((((()))))) ) programs feel.

Optimize THIS

The syntax highlighter gets   it horribly wrong.

23 Name: Anonymous 2010-11-15 16:56

25 Name: Sgt.Kabukimanꘃ௦ 2012-05-28 21:49

Bringing /prog/ back to its people
All work and no play makes Jack a dull boy
All work and no play makes Jack a dull boy
All work and no play makes Jack a dull boy
All work and no play makes Jack a dull boy
All work and no play makes Jack a dull boy
All work and no play makes Jack a dull boy
All work and no play makes Jack a dull boy
All work and no play makes Jack a dull boy

---

Don't change these.

Name:		Email:
Entire Thread Thread List