1. Registered User
Join Date
May 2009
Posts
9

## Is Prime Help

I am making a program that takes user input and then returns either true of false based on whether the number entered is prime. Prime = True, Not Prime = False. I am having trouble with the red colored code that follows. More specifically. The math is correct i think but I'm missing something.

<script type="text/javascript">

function frontWork() {
var n = parseFloat(document.getElementById("inBox").value);
var output = isPrime(n);
document.getElementById("outBox").value=output;
}

function isPrime(n) {
if (n == 1 || n == 2){
return true;
}

for (var i=2;i<n;i++) {
if (num &#37; i == 0) {
return true;
break;

}
if (n % i != 0) {
return false;
}
else {
return true;
}
}

}
</script>
Last edited by Jaxyral; 05-21-2009 at 09:19 AM.

2. You've a syntax error there--and you're making things more difficult than you need.
Code:
```Number.prototype.isPrime = function () {
var n = Math.abs (this);
for (var i = 2; i < n; i++) if (n &#37; i == 0) return false;
return true;
}

n = Number (prompt ('Number', ''));
alert (n.isPrime() ? 'Prime' : 'Not prime');```

3. Registered User
Join Date
May 2009
Posts
150
That can be optimised as numbers above the root of a number are only factors if a number below the root is a factor too (as they will be multiplied together):

Code:
```Number.prototype.isPrime = function ()
{
var
n = Math.abs(this), m = Math.sqrt(n), i = 1;
while (++i <= m)
{
if (!(n &#37; i))
{
return false;
}
}
return true;
}

n = Number (prompt ('Number', ''));
alert (n.isPrime() ? 'Prime' : 'Not prime');```

4. Registered User+
Join Date
Aug 2007
Posts
3,767
And you can immediately reduce the number of modulus tests by half if you test for two separately. You can do the same trick indefinetly obviously, but it's most efficient for two IMO.
Code:
```function isPrime(n) {
n = Math.abs(n);
var l = Math.sqrt(n);
if (n&#37;2) return false;
for (i = 3; i < m; i += 2) {
if (!(n % i)) {
return false;
}
}
return true;
}```
Also, using closures, if generating a list of primes, you can store the primes already found in an array, and you only have to test the next number with those primes up to the square root of the number, a very efficient way to generate a list of primes. Also, you can use facts like, all primes will either be 6n + 1 or 6n - 1 to speed up the process.

5. Watch out the typo! :
Code:
```function isPrime(n) {
n = Math.abs(n);
var l = Math.sqrt(n);
if (n&#37;2) return false;
for (i = 3; i < m; i += 2) {
if (!(n % i)) {
return false;
}
}
return true;
}```
Last edited by Kor; 01-13-2010 at 08:44 AM.

6. Registered User+
Join Date
Aug 2007
Posts
3,767
Code:
```function primes(n) {
n = Math.abs(n);
if (n&#37;2==0 || n%3==0)
return false;
for (var i = 6, l = Math.sqrt(n)+1; i < l; i+=6) {
if (n%(i+1) == 0 || n%(i+1) == 0) {
return false;
}
}
return true;
}```
That's the one I've been using recently. Quickest I know bar functions for generating primes.

7. Registered User
Join Date
May 2009
Posts
150
Why do you do an or with two identical conditionals?

8. Registered User+
Join Date
Aug 2007
Posts
3,767
What is with my typos in this thread!
Code:
```function primes(n) {
n = Math.abs(n);
if (n&#37;2==0 || n%3==0)
return false;
for (var i = 6, l = Math.sqrt(n)+1; i < l; i+=6) {
if (n%(i+1) == 0 || n%(i-1) == 0) {
return false;
}
}
return true;
}```

9. Registered User+
Join Date
Feb 2006
Posts
2,930
Something's not right with Declan's code-
it returns true for the following non-prime numbers:
1, 2, 3, 25, 121, 289, 529, 841, 1681, 2209, 2809, 3481, 5041, 6889, 7921, 10201, 11449, 12769, 17161, 18769, 22201, 27889, 29929, 32041, 36481, 38809, 51529, 54289, 57121, 63001, 66049, 69169, 72361, 78961, 85849, 96721

Both of your functions call 0 and 1 prime numbers, as well as most decimals and negative numbers, which cannot by definition be prime.

I stick with Erotosthenes, who wrote this for an earlier form of javascript :

Code:
```Number.prototype.isPrime= function(){
if(this== 2) return true;
var n= Math.floor(this);
if(n!= this || this< 3 || !(this&#37;2)) return false;

var i= 3, limit= Math.sqrt(n)+1;
while(i< limit){
if(!(n%i)) return false;
i+= 2;
}
return true;
}```
Half the code is to check for special cases- numbers less than 3 or divisible by 2 that are not 2, and non-integers.

In mathematics, a prime number (or a prime) is a natural number that has exactly two distinct natural number divisors: 1 and itself

There are two conventions for the set of natural numbers: it is either the set of positive integers {1, 2, 3, ...}
according to the traditional definition or the set of non-negative integers {0, 1, 2, ...}
Last edited by mrhoo; 01-13-2010 at 01:47 PM.

10. Registered User+
Join Date
Aug 2007
Posts
3,767
Ah I see my problem, I was trying prime generator trick (all primes are in the form 6n+-1) to reduce the number of division tests I had to use. Obviously it doesn't work.

And, by the way, 2 and 3 are prime.

If anyone is interested, this is the principle I mistakenly tried to implement (using JavaScript v1.8's generator functions). That definetly works because I have used it, and didn't have to alter it.
Code:
```function primes() {
yield 2;
yield 3;
let p = [2,3], flag;
for (let n = 6;; n+=6) {
flag = true;
let s = Math.sqrt(n)+1, t = n-1;
for (let i = 0; p[i]< s; i++) {
if (t&#37;p[i] == 0) {
flag = false;
break;
}
}
if (flag) {
yield t;
p[p.length] = t;
}
flag = true;
t = n+1;
for (let i = 0; p[i]< s; i++) {
if (t%p[i] == 0) {
flag = false;
break;
}
}
if (flag) {
yield t;
p[p.length] = t;
}
}
}```

11. Registered User+
Join Date
Feb 2006
Posts
2,930
It is strange that it almost worked- there are 9592 primes below 100,000 and your method correctly identified
all the intergers that are prime (yes, including 2 and 3 and only mis-called those 20 odd.
Last edited by mrhoo; 01-13-2010 at 07:01 PM.

12. Registered User+
Join Date
Aug 2007
Posts
3,767
I figured it out. The problem was square numbers (in particular (6n-1)^2). Take 25. The square-root plus one is 6. The for loop then wouldn't run, which let it through. This code (or I presume using i <= l instead of <) works for sure. And this time I tested on numbers that weren't prime as well as those that are .
Code:
```function isPrime(n) {
n = Math.abs(n);
if (n == 2 || n == 3) return true;
if (n&#37;2==0 || n%3==0 || n < 3) return false;
for (var i = 5, l = Math.sqrt(n)+1; i < l; i+=6) {
if (n%(i) == 0 || n%(i+2) == 0) {
return false;
}
}
return true;
}```
I was trying to get a more efficient function, but that's probably negligible. The loop is slightly refractored, and for big numbers, it only has 2/3 of the modulus tests to do, but it has more to do initially.
Last edited by Declan1991; 01-14-2010 at 01:15 PM.

13. Registered User+
Join Date
Feb 2006
Posts
2,930
Thank you for catching that, Declan, and explaining it- a method that works 99 percent of the time drives me nuts- I hadn't unraveled the squares yet. Nice job.

14. Registered User+
Join Date
Aug 2007
Posts
3,767
I was getting worried, I'd posted three functions in this thread, and none worked!

15. Here's a development (written by rnd me), following your idea:

Number.prototype.isPrime

Code:
```(function(){function isPrime(){ var n=this;
if(isPrime[n]){ return true; }
if( n<11|| ! ((n&#37;2)&&(n%3)&&(n%7)&&(n%9)) ){ return false; }
for (var i=5, l=Math.sqrt(n)+1; i<l; i+=6){
if( !(n%i) || !(n%(i+2)) ){ return false; }
}
return isPrime.n++ < 1e6 ? (isPrime[n]=true) : true;
}; var p=isPrime;p.n=0;p[2]=p[3]=p[5]=p[7]=true; Number.prototype.isPrime=p;
}());```

There are currently 1 users browsing this thread. (0 members and 1 guests)

#### Posting Permissions

• You may not post new threads
• You may not post replies
• You may not post attachments
• You may not edit your posts
•

"

"

## X vBulletin 4.2.2 Debug Information

• Page Generation 0.20494 seconds
• Memory Usage 3,005KB
• Queries Executed 13 (?)
Template Usage (33):
• (10)bbcode_code
• (1)footer
• (1)forumjump
• (1)forumrules
• (1)gobutton
• (15)memberaction_dropdown
• (1)navbar
• (1)navbar_moderation
• (1)navbar_noticebit
• (1)navbar_tabs
• (2)option
• (15)postbit
• (15)postbit_onlinestatus
• (15)postbit_wrapper
• (1)spacer_close
• (1)spacer_open
• (1)tagbit_wrapper

Phrase Groups Available (6):
• global
• inlinemod
• postbit
• posting
• reputationlevel
Included Files (26):
• ./global.php
• ./includes/class_bootstrap.php
• ./includes/init.php
• ./includes/class_core.php
• ./includes/config.php
• ./includes/functions.php
• ./includes/class_friendly_url.php
• ./includes/class_hook.php
• ./includes/class_bootstrap_framework.php
• ./vb/vb.php
• ./vb/phrase.php
• ./includes/functions_calendar.php
• ./includes/functions_bigthree.php
• ./includes/class_postbit.php
• ./includes/class_bbcode.php
• ./includes/functions_reputation.php
• ./includes/functions_notice.php
• ./packages/vbattach/attach.php
• ./vb/types.php
• ./vb/cache.php
• ./vb/cache/db.php
• ./vb/cache/observer/db.php
• ./vb/cache/observer.php

Hooks Called (70):
• init_startup
• friendlyurl_resolve_class
• init_startup_session_setup_start
• database_pre_fetch_array
• database_post_fetch_array
• init_startup_session_setup_complete
• global_bootstrap_init_start
• global_bootstrap_init_complete
• cache_permissions
• fetch_foruminfo
• global_state_check
• global_bootstrap_complete
• global_start
• style_fetch
• global_setup_complete
• strip_bbcode
• friendlyurl_clean_fragment
• friendlyurl_geturl
• forumjump
• cache_templates
• cache_templates_process
• template_register_var
• template_render_output
• fetch_template_start
• fetch_template_complete
• parse_templates
• notices_check_start
• notices_noticebit
• process_templates_complete
• friendlyurl_redirect_canonical
• bbcode_fetch_tags
• bbcode_create
• postbit_factory
• postbit_display_start
• postbit_imicons
• bbcode_parse_start
• bbcode_parse_complete_precache
• bbcode_parse_complete
• postbit_display_complete
• memberaction_dropdown
• tag_fetchbit_complete
• forumrules
• navbits
• navbits_complete