Need a clever algorithm
Mike B
(http://members.lycos.co.uk/pholcroft/java/sieve.java) but I'm obsessive
about it and the program doesn't space its output properly.
So I've started to write extra code into the program to space the numbers
properly. Yea I know, it'll make it run slower, but I'm not looking for the
largest prime number, I'm just messing in a toybox.
My thinking is along the following lines (some code to follow):
Find out what the upper bound of the prime number search is.
Find out how many digits the upper bound is.
find out how many times I can write the number (with a space between each
successive number) in a cmd-window line (80 characters).
That I can do. The hard part is to put enough spaces in front of each number
so they'll line up properly. In prior code I used nested if statements to
insert the right number of spaces, but I'd rather find a clever way that
does not rely on the correct number of nested if statements. In other words,
if I make it work for prime numbers less than 1000, I don't want to code
additional nested if statements to make it work for prime numbers under
10,000.
Any ideas?
Here is some code
<sscce>
import java.lang.*;
import java.util.Arrays;
class Prime {
static final int max = 1000; // Set the size of the problem
static final int startat = max - 1000; // Display primes from this value
static int n = max;
static double limit;
static int primeCount;
public static void main (String [] args) {
String strMax = Integer.toString(max);
int intMaxLen = strMax.length();
int intColumns = (80 / intMaxLen);
System.out.println("intMaxLen=" + intMaxLen + " gives " + intColumns);
int intPowerOfTen= 0;
for (int i = max; i > 1; i /= 10)
{
intPowerOfTen++;
}
System.out.println(max + "is 10 to the " + intPowerOfTen);
// Create array and set all values to true
boolean numberPool [] = new boolean [n];
Arrays.fill(numberPool, true);
limit = Math.sqrt(n); // Find square root of n
int j=2; // do all multiples of 2 first
System.out.println("for (int i=" + (j+j) + "; i<" + n + "; i=i+" + j);
for (int i=j+j; i<n; i=i+j){ // start with 2j as j is prime
numberPool[i]=false; // set all multiples to false
}
System.out.println("(for (j=3; j<=" + limit + "; j=j+2)\n");
for (j=3; j<=limit; j=j+2){ // do up to sqrt of n
if (numberPool[j]==true){ // only do if j is a prime
for (int i=j+j; i<n; i=i+j){ // start with 2j as j is prime
numberPool[i]=false; // set all multiples to false
}
}
}
// Display results
System.out.println("Prime Numbers from " + startat + " to " + max +
":");
for (int i=startat; i<max; i++){
if (numberPool[i]==true){
primeCount++;
//
// insert an insanely clever algorithm here to avoid nested if loops in
formatting text.
//
System.out.print(i + " ");
}
}
System.out.println("\n\nI found " + primeCount + " prime numbers.");
}
}
</sscce>
--
Mike B
jmm-list-gn
> I'm messing around in Java. Found an interesting prime number generator here
> (http://members.lycos.co.uk/pholcroft/java/sieve.java) but I'm obsessive
> about it and the program doesn't space its output properly.
>
--
jmm dash list (at) sohnen-moe (dot) com
(Remove .AXSPAMGN for email)
Mike B
> Use java.text.NumberFormat.
Thanks! I did that, and now I broke something that I can't figure out. I'm
getting a StringIndexOutOfBoundsException when I'm trying to process the
string "0011". Any idea?
Exception in thread "main" java.lang.StringIndexOutOfBoundsException: String
index out of range: 4
at java.lang.StringBuffer.charAt(StringBuffer.java:163)
at Prime.main(Prime.java:81)
<sscce>
import java.lang.*;
import java.util.Arrays;
import java.text.NumberFormat;
class Prime {
static final int max = 1000; // Set the size of the problem
static final int startat = max - 1000; // Display primes from this value
static int n = max;
static double limit;
static int primeCount;
static char zero = '0';
static char space = ' ';
public static void main (String [] args) {
String strMax = Integer.toString(max);
int intMaxLen = strMax.length();
int intColumns = (80 / intMaxLen);
System.out.println("intMaxLen=" + intMaxLen + " gives " + intColumns);
NumberFormat number = NumberFormat.getIntegerInstance();
number.setMinimumIntegerDigits(intMaxLen);
number.setGroupingUsed(false);
// Create array and set all values to true
boolean numberPool [] = new boolean [n];
Arrays.fill(numberPool, true);
limit = Math.sqrt(n); // Find square root of n
int j=2; // do all multiples of 2 first
System.out.println("for (int i=" + (j+j) + "; i<" + n + "; i=i+" + j);
for (int i=j+j; i<n; i=i+j){ // start with 2j as j is prime
numberPool[i]=false; // set all multiples to false
}
System.out.println("(for (j=3; j<=" + limit + "; j=j+2)\n");
for (j=3; j<=limit; j=j+2){ // do up to sqrt of n
if (numberPool[j]==true){ // only do if j is a prime
for (int i=j+j; i<n; i=i+j){ // start with 2j as j is prime
numberPool[i]=false; // set all multiples to false
}
}
}
// Display results
System.out.println("Prime Numbers from " + startat + " to " + max +
":");
for (int i=startat; i<max; i++){
if (numberPool[i]==true)
{
primeCount++;
StringBuffer sbNumber = new StringBuffer(number.format(i));
Boolean foundSignificantDigit = false;
System.out.println("int k=0;(k<" + (sbNumber.length() - 1) + ")
|| ("+ (foundSignificantDigit) + ");k++)");
for (int k=0;(k<(sbNumber.length() - 1))||
(foundSignificantDigit);k++)
{
System.out.println("sbNumber.charAt(" + k + ")="+ sbNumber.charAt(k));
if (sbNumber.charAt(k) == '0')
{
sbNumber.setCharAt(k, ' ');
}
else
{
foundSignificantDigit = true;
}
}
System.out.print(sbNumber + " ");
// System.out.print(number.format(i) + " ");
Starshine Moonbeam
nom...@nomail.yahoo.com) dropped a +5 bundle of words...
> jmm-list-gn <jmm-list...@sohnen-moe.com> wrote:
>
> > Use java.text.NumberFormat.
>
> Thanks! I did that, and now I broke something that I can't figure out. I'm
> getting a StringIndexOutOfBoundsException when I'm trying to process the
> string "0011". Any idea?
>
> Exception in thread "main" java.lang.StringIndexOutOfBoundsException: String
> index out of range: 4
> at java.lang.StringBuffer.charAt(StringBuffer.java:163)
> at Prime.main(Prime.java:81)
It means you went past either the low or high index for your search.
Prime class, line 81
--
Starshine Moonbeam
mhm31x9 Smeeter#29 WSD#30
sTaRShInE_mOOnBeAm aT HoTmAil dOt CoM
Mike B
> In article <41b16...@news1.prserv.net>, Mike B (mrcics2000-news-
> nom...@nomail.yahoo.com) dropped a +5 bundle of words...
>
>> jmm-list-gn <jmm-list...@sohnen-moe.com> wrote:
>>
>>> Use java.text.NumberFormat.
>>
>> Thanks! I did that, and now I broke something that I can't figure
>> out. I'm getting a StringIndexOutOfBoundsException when I'm trying
>> to process the string "0011". Any idea?
>>
>> Exception in thread "main"
>> java.lang.StringIndexOutOfBoundsException: String index out of
>> range: 4 at
>> java.lang.StringBuffer.charAt(StringBuffer.java:163) at
>> Prime.main(Prime.java:81)
>
> It means you went past either the low or high index for your search.
>
> Prime class, line 81
Thank you. I know that much. What I can't figure out is how that could
happen. It seems as if the compare doesn't work, whereas it did work in the
previous iterations of the loop.
--
Mike B
Mike B
I found the problem! Whew, that was hard. See comments.
// This conditional is wrong! very wrong. It took me a lot of testing to
find the problem, but it should be
for (int k=0;(k<(sbNumber.length() - 1)) &&
(!foundSignificantDigit);k++)